Chaining together entries into groups
The output of your CTE is inconsistent: john, paul, and ringo have different numbers of band members. You should go through the pairs in both directions (and then use UNION to prevent duplicates and infinite loops):

with bands (member, leader) as (
    select item1, item2 from pairs
    union
    select item2, item1 from pairs
    union
    select ... -- recursion
) ...


Now you have all possible combinations of leaders and band members, but you want only one (random but unique) leader per band. So for all rows with the same band member, choose the one with the smallest leader:

with bands as (...)
select 'group:'||min(leader), member
from bands
group by member
order by min(leader);