소어그래프

문제 정보
시간 제한	메모리 제한	공개일
1000 ms	1024 MB	2025년 7월 12일

문제

정점의 개수가 $$N$$ 인 소어그래프(XOR Graph)는 다음과 같이 정의된다.

소어그래프는 $$0$$ 부터 $$N-1$$ 까지의 번호가 붙은 $$N$$ 개의 정점을 가진다.
각 정점 $$i$$ 에 대해, 정점 $$i$$ 에서 정점 $i\oplus t$ 와 정점 $(i\oplus t)+1$ 로 가는 방향 간선이 존재한다.
단, 간선을 통해 이동하려는 도착 정점의 번호가 $$N-1$$ 을 초과하는 경우, 해당 간선은 존재하지 않는다.

여기서 $\oplus$ 기호는 Bitwise XOR을 나타낸다.

정점의 개수 $$N$$ , 시작 정점 $$x$$ , 도착 정점 $$y$$ , 그리고 음이 아닌 정수 $$t$$ 가 주어질 때, 정점 $$x$$ 에서 정점 $$y$$ 로 이동하기 위해 지나야 하는 간선의 최소 개수를 구하는 프로그램을 작성하라.

첫째 줄에 정수 $$N$$ , $$x$$ , $$y$$ , $$t$$ 가 공백으로 구분되어 주어진다. ( $2 \leq N \leq 10^{18}$ ; $0 \leq x, y < N$ ; $x \neq y$ ; $0 \leq t < 2^{20}$ )

정점 $$x$$ 에서 정점 $$y$$ 로 이동하기 위해 지나야 하는 간선의 최소 개수를 출력한다. 만약 정점 $$x$$ 에서 정점 $$y$$ 로 가는 경로가 존재하지 않는다면 $$-1$$ 을 출력한다.