SQL Server 2017

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.

with t as (
      select v.*
      from (values (1, 1111, 2222),
                   (2, 2222, 3333),
                   (3, 3333, 1111),
                   (4, 4444, 5555),
                   (5, 2222, 1111),
                   (6, 5555, 1111),
                   (7, 6666, 8888),
                   (8, 7777, 9999)
           ) v(pk, id1, id2)
    ),
    cte as (
     select pk, id1, id1 as id2, convert(varchar(max), concat(',', id1, ',')) as visited
     from t
     union all
     select cte.pk, cte.id1, t.id2, convert(varchar(max), concat(visited, t.id2, ','))
     from cte join
          t
          on cte.id2 = t.id1
     where cte.visited not like concat('%,', t.id2, ',%')  
     union all
     select cte.pk, cte.id1, t.id1, convert(varchar(max), concat(visited, t.id1, ','))
     from cte join
          t
          on cte.id2 = t.id2
     where cte.visited not like concat('%,', t.id1, ',%')  
    )
     
select pk, id1, min(id2), dense_rank() over (order by min(id2))
from cte
group by pk, id1

pk	id1	(No column name)	(No column name)
1	1111	1111	1
2	2222	1111	1
5	2222	1111	1
3	3333	1111	1
4	4444	1111	1
6	5555	1111	1
7	6666	6666	2
8	7777	7777	3