문제
정점의 개수가 $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$로 이동하기 위해 지나야 하는 간선의 최소 개수를 구하는 프로그램을 작성하라.
출력
정점 $x$에서 정점 $y$로 이동하기 위해 지나야 하는 간선의 최소 개수를 출력한다. 만약 정점 $x$에서 정점 $y$로 가는 경로가 존재하지 않는다면 $-1$을 출력한다.
W3sicHJvYmxlbV9pZCI6IjM0MDYxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVjNWI0XHVhZGY4XHViNzk4XHVkNTA0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwICROJFx1Yzc3OCBcdWMxOGNcdWM1YjRcdWFkZjhcdWI3OThcdWQ1MDQoWE9SIEdyYXBoKVx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWMxOGNcdWM1YjRcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgJDAkXHViZDgwXHVkMTMwICROLTEkXHVhZTRjXHVjOWMwXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM3NDAgJE4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWFjMDBcdWM5YzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWMwMSBcdWM4MTVcdWM4MTAgJGkkXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjODE1XHVjODEwICRpJFx1YzVkMFx1YzExYyBcdWM4MTVcdWM4MTAgJGlcXG9wbHVzIHQkXHVjNjQwIFx1YzgxNVx1YzgxMCAkKGlcXG9wbHVzIHQpICsxJFx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViYzI5XHVkNWE1IFx1YWMwNFx1YzEyMFx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjJlOCwgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1ZDFiNVx1ZDU3NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWIyOTQgXHViM2M0XHVjYzI5IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgJE4tMSRcdWM3NDQgXHVjZDA4XHVhY2ZjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMCwgXHVkNTc0XHViMmY5IFx1YWMwNFx1YzEyMFx1Yzc0MCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YzExYyAkXFxvcGx1cyQgXHVhZTMwXHVkNjM4XHViMjk0IDxhIGhyZWY9XCJodHRwczpcL1wvZW4ud2lraXBlZGlhLm9yZ1wvd2lraVwvQml0d2lzZV9vcGVyYXRpb24jWE9SXCI+Qml0d2lzZSBYT1I8XC9hPlx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggJE4kLCBcdWMyZGNcdWM3OTEgXHVjODE1XHVjODEwICR4JCwgXHViM2M0XHVjYzI5IFx1YzgxNVx1YzgxMCAkeSQsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOCAkdCRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgXHVjODE1XHVjODEwICR4JFx1YzVkMFx1YzExYyBcdWM4MTVcdWM4MTAgJHkkXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjOWMwXHViMDk4XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWFjMDRcdWMxMjBcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4ICROJCwgJHgkLCAkeSQsICR0JFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQyIFxcbGVxIE4gXFxsZXEgMTBeezE4fSQ7ICQwIFxcbGVxIHgsIHkgJmx0OyBOJDsgJHggXFxuZXEgeSQ7ICQwIFxcbGVxIHQgJmx0OyAyXnsyMH0kKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzgxNVx1YzgxMCAkeCRcdWM1ZDBcdWMxMWMgXHVjODE1XHVjODEwICR5JFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzljMFx1YjA5OFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjODE1XHVjODEwICR4JFx1YzVkMFx1YzExYyBcdWM4MTVcdWM4MTAgJHkkXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCAkLTEkXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9mOTU2MDkwMC01ODQyLTQ3YjktYTBkYy00ZDUzYzRmYTRhOTNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwiaGVpZ2h0OiAyOTVweDsgd2lkdGg6IDQwMHB4O1wiIFwvPjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjM0MDYxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWE9SIEdyYXBoIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBYT1IgZ3JhcGggd2l0aCAkTiQgdmVydGljZXMgaXMgZGVmaW5lZCBhcyBmb2xsb3dzLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBncmFwaCBoYXMgJE4kIHZlcnRpY2VzIG51bWJlcmVkIGZyb20gJDAkIHRvICROLTEkLjxcL2xpPlxyXG5cdDxsaT5Gb3IgZWFjaCB2ZXJ0ZXggJGkkLCB0aGVyZSBhcmUgZGlyZWN0ZWQgZWRnZXMgZnJvbSB2ZXJ0ZXggJGkkIHRvIHZlcnRleCAkaVxcb3BsdXMgdCQgYW5kIHZlcnRleCAkKGlcXG9wbHVzIHQpICsxJC48XC9saT5cclxuXHQ8bGk+SG93ZXZlciwgaWYgdGhlIGRlc3RpbmF0aW9uIHZlcnRleCBleGNlZWRzICROLTEkLCB0aGUgZWRnZSBkb2VzIG5vdCBleGlzdC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5IZXJlLCAkXFxvcGx1cyQgZGVub3RlcyB0aGUgPGEgaHJlZj1cImh0dHBzOlwvXC9lbi53aWtpcGVkaWEub3JnXC93aWtpXC9CaXR3aXNlX29wZXJhdGlvbiNYT1JcIj5iaXR3aXNlIFhPUjxcL2E+IG9wZXJhdGlvbi48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyAkTiQsIHRoZSBzdGFydGluZyB2ZXJ0ZXggJHgkLCB0aGUgZGVzdGluYXRpb24gdmVydGV4ICR5JCwgYW5kIGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgJHQkLCBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBlZGdlcyBuZWVkZWQgdG8gbW92ZSBmcm9tIHZlcnRleCAkeCQgdG8gdmVydGV4ICR5JC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGZvdXIgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICROJCwgJHgkLCAkeSQsIGFuZCAkdCQuICgkMiBcXGxlcSBOIFxcbGVxIDEwXnsxOH0kOyAkMCBcXGxlcSB4LCB5ICZsdDsgTiQ7ICR4IFxcbmVxIHkkOyAkMCBcXGxlcSB0ICZsdDsgMl57MjB9JCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0aGUgbWluaW11bSBudW1iZXIgb2YgZWRnZXMgbmVlZGVkIHRvIG1vdmUgZnJvbSB2ZXJ0ZXggJHgkIHRvIHZlcnRleCAkeSQuIElmIG5vIHN1Y2ggcGF0aCBleGlzdHMsIHByaW50ICQtMSQgaW5zdGVhZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNGI2YzVkYTUtYjExMi00ZGNkLTlkMzctMjk0NTJhZjJjMDhhXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cImhlaWdodDogMjk1cHg7IHdpZHRoOiA0MDBweDtcIiBcLz48XC9wPlxyXG4ifV0=