백준 온라인 저지, 분리집합 / 7511번: 소셜네트워킹어플리케이션 (파이썬 / , 백준 골드문제)

문제

어렸을때부터 컴퓨터 프로그래밍에 엄청난 소질을 보인 상근이는 항상 소셜 네트워킹 웹사이트를 만들고 싶어 했다. 상근이는 페이스북을 벤치마킹하기 위해 지난 3년간 열심히 사용을 했고, 이제 페이스북의 단점을 보완한 새 소셜 네트워킹 웹 2.0 어플리케이션을 만들려고 한다.

사람들은 소셜 네트워킹 어플리케이션에 가입을 한 다음, 현실에서 아는 사람을 친구로 추가하기 시작한다. 이러한 친구 관계 정보를 이용해 친구 관계 그래프를 그릴 수 있다.

소셜 네트워킹 어플리케이션에서 가장 중요한 기능은 한 사람이 다른 사람의 페이지를 방문했을 때, 친구 관계 그래프에서 두 사람 사이의 경로를 보여주는 기능이다. 경로가 없는 경우에는 보여주지 않는다.

상근이의 서비스는 매우 유명해졌고, 위의 기능은 사람들이 점점 많아질수록 경로를 구하는 시간이 매우 느려지게 되었다. 그 이유는 두 사람 사이의 경로가 없는 경우에 경로를 찾기 위해 너무 오랜시간 그래프를 탐색하기 때문이었다. 따라서, 상근이는 두 사람 사이의 경로가 존재하는지 안 하는지를 미리 구해보려고 한다.

유저의 수와 각 유저의 친구 관계가 입력으로 주어진다. 이때, 주어지는 두 사람이 친구 관계 그래프상에서 경로가 존재하는지 안 하는지를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 유저의 수 1 ≤ n ≤ 10⁶이 주어진다. 둘째 줄에는 친구 관계의 수 1 ≤ k ≤ 10⁵가 주어진다. 다음 k개 줄에는 두 정수 0 ≤ a, b < n이 주어진다. 두 수는 친구 관계를 나타내며, 유저 a와 b가 친구라는 소리이다. 다음 줄에는 미리 구할 쌍의 수 1 ≤ m ≤ 10⁵가 주어진다. 다음 m개 줄에는 구해야하는 쌍을 나타내는 u, v가 주어진다.

출력

각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

제한

예제 입력 1

2
3
1
0 1
2
0 1
1 2
5
3
0 1
1 2
3 4
2
0 2
1 3

예제 출력 1

Scenario 1:
1
0

Scenario 2:
1
0

힌트

W3sicHJvYmxlbV9pZCI6Ijc1MTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMxNWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMGI5IFx1YzViNFx1ZDUwY1x1YjlhY1x1Y2YwMFx1Yzc3NFx1YzE1OCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWI0XHViODM4XHVjNzQ0XHViNTRjXHViZDgwXHVkMTMwIFx1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGRcdWM1ZDAgXHVjNWM0XHVjY2FkXHViMDljIFx1YzE4Y1x1YzljOFx1Yzc0NCBcdWJjZjRcdWM3NzggXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWMxOGNcdWMxNWMgXHViMTI0XHVkMmI4XHVjNmNjXHVkMGI5IFx1YzZmOVx1YzBhY1x1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjMmY2XHVjNWI0IFx1ZDU4OFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDM5OFx1Yzc3NFx1YzJhNFx1YmQ4MVx1Yzc0NCBcdWJjYTRcdWNlNThcdWI5YzhcdWQwYjlcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzljMFx1YjA5YyAzXHViMTQ0XHVhYzA0IFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWMwYWNcdWM2YTlcdWM3NDQgXHVkNTg4XHVhY2UwLCBcdWM3NzRcdWM4MWMgXHVkMzk4XHVjNzc0XHVjMmE0XHViZDgxXHVjNzU4IFx1YjJlOFx1YzgxMFx1Yzc0NCBcdWJjZjRcdWM2NDRcdWQ1NWMgXHVjMGM4IFx1YzE4Y1x1YzE1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwYjkgXHVjNmY5IDIuMCBcdWM1YjRcdWQ1MGNcdWI5YWNcdWNmMDBcdWM3NzRcdWMxNThcdWM3NDQgXHViOWNjXHViNGU0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YzE4Y1x1YzE1YyBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwYjkgXHVjNWI0XHVkNTBjXHViOWFjXHVjZjAwXHVjNzc0XHVjMTU4XHVjNWQwIFx1YWMwMFx1Yzc4NVx1Yzc0NCBcdWQ1NWMgXHViMmU0XHVjNzRjLCBcdWQ2MDRcdWMyZTRcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWNlNWNcdWFkNmNcdWI4NWMgXHVjZDk0XHVhYzAwXHVkNTU4XHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1Y2U1Y1x1YWQ2YyBcdWFkMDBcdWFjYzQgXHVjODE1XHViY2Y0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWFkZjhcdWI5YjQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMThjXHVjMTVjIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDBiOSBcdWM1YjRcdWQ1MGNcdWI5YWNcdWNmMDBcdWM3NzRcdWMxNThcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzkxMVx1YzY5NFx1ZDU1YyBcdWFlMzBcdWIyYTVcdWM3NDAgXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWIyZTRcdWI5NzggXHVjMGFjXHViNzhjXHVjNzU4IFx1ZDM5OFx1Yzc3NFx1YzljMFx1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YzVkMFx1YzExYyBcdWI0NTAgXHVjMGFjXHViNzhjIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWI5N2MgXHViY2Y0XHVjNWVjXHVjOGZjXHViMjk0IFx1YWUzMFx1YjJhNVx1Yzc3NFx1YjJlNC4gXHVhY2JkXHViODVjXHVhYzAwIFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViY2Y0XHVjNWVjXHVjOGZjXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzExY1x1YmU0NFx1YzJhNFx1YjI5NCBcdWI5ZTRcdWM2YjAgXHVjNzIwXHViYTg1XHVkNTc0XHVjODRjXHVhY2UwLCBcdWM3MDRcdWM3NTggXHVhZTMwXHViMmE1XHVjNzQwIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWM4MTBcdWM4MTAgXHViOWNlXHVjNTQ0XHVjOWM4XHVjMjE4XHViODVkIFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjllNFx1YzZiMCBcdWIyOTBcdWI4MjRcdWM5YzBcdWFjOGMgXHViNDE4XHVjNWM4XHViMmU0LiBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IFx1YjQ1MCBcdWMwYWNcdWI3OGMgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNjM2VcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjEwOFx1YmIzNCBcdWM2MjRcdWI3OWNcdWMyZGNcdWFjMDQgXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIFx1ZDBkMFx1YzBjOVx1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWM1YzhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWMwYWNcdWI3OGMgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNTQ4IFx1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWJiZjhcdWI5YWMgXHVhZDZjXHVkNTc0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzIwXHVjODAwXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWFjMDEgXHVjNzIwXHVjODAwXHVjNzU4IFx1Y2U1Y1x1YWQ2YyBcdWFkMDBcdWFjYzRcdWFjMDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YzBjMVx1YzVkMFx1YzExYyBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHVjOWMwIFx1YzU0OCBcdWQ1NThcdWIyOTRcdWM5YzBcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzIwXHVjODAwXHVjNzU4IFx1YzIxOCAxICZsZTsgbiAmbGU7IDEwPHN1cD42PFwvc3VwPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjZTVjXHVhZDZjIFx1YWQwMFx1YWNjNFx1Yzc1OCBcdWMyMTggMSAmbGU7IGsgJmxlOyAxMDxzdXA+NTxcL3N1cD5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMga1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCAwICZsZTsgYSwgYiAmbHQ7IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NTAgXHVjMjE4XHViMjk0IFx1Y2U1Y1x1YWQ2YyBcdWFkMDBcdWFjYzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWM3MjBcdWM4MDAgYVx1YzY0MCBiXHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1Yjc3Y1x1YjI5NCBcdWMxOGNcdWI5YWNcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYmY4XHViOWFjIFx1YWQ2Y1x1ZDU2MCBcdWMzMGRcdWM3NTggXHVjMjE4IDEgJmxlOyBtICZsZTsgMTA8c3VwPjU8XC9zdXA+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWQ2Y1x1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWMzMGRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IHUsIHZcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0ICZxdW90O1NjZW5hcmlvIGk6JnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gaVx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YmE3MCwgMVx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YWRmOCBcdWIyZTRcdWM3NGMsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMzMGRcdWI5YzhcdWIyZTQgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1Yzc4OFx1YzczY1x1YmE3NCAxLCBcdWM1YzZcdWM3M2NcdWJhNzQgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWJlNDggXHVjOTA0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNzUxMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IiIsImRlc2NyaXB0aW9uIjoiPHA+TWFyayBpcyBhIHByZXR0eSBjb29sIGd1eSAtIGhlIHByb2dyYW1zIGNvbXB1dGVycy4gQmVjYXVzZSBpdCZyc3F1bztzIGFsbCB0aGUgcmFnZSB0aGVzZSBkYXlzLCBoZSBoYXMgZGVjaWRlZCB0byB3cml0ZSBhIHNvY2lhbC1uZXR3b3JraW5nIHdlYjIuMCBhcHBsaWNhdGlvbi4gSW4gYSBzb2NpYWwtbmV0d29ya2luZyBhcHBsaWNhdGlvbiwgdXNlcnMgbWF5IG9wZW4gYWNjb3VudHMgYW5kIHRlbGwgdGhlIHN5c3RlbSB3aGljaCBvdGhlciB1c2VycyB0aGV5IGNvbnNpZGVyIGFzIGZyaWVuZHMuIFRoaXMgZnJpZW5kc2hpcCBpbmZvcm1hdGlvbiBkZVx1ZmIwMW5lcyB0aGUgZnJpZW5kc2hpcCBncmFwaCBvZiB0aGUgbmV0d29yay48XC9wPlxyXG5cclxuPHA+QW4gaW1wb3J0YW50IGZlYXR1cmUgb2Ygc29jaWFsIG5ldHdvcmtpbmcgYXBwbGljYXRpb25zIGlzIHRoYXQgd2hlbmV2ZXIgYSB1c2VyIHZpc2l0cyB0aGUgcGFnZSBvZiBhbm90aGVyIHVzZXIsIHRoZSBzeXN0ZW0gd2lsbCBkZXRlcm1pbmUgd2hldGhlciB0aGVyZSBpcyBhIHBhdGggaW4gdGhlIGZyaWVuZHNoaXAgZ3JhcGggZnJvbSB0aGUgXHVmYjAxcnN0IHRvIHRoZSBzZWNvbmQgdXNlci4gSWYgc28sIG9uZSBzdWNoIGEgZnJpZW5kc2hpcCBwYXRoIGlzIGRpc3BsYXllZC48XC9wPlxyXG5cclxuPHA+TWFyayZyc3F1bztzIHNvY2lhbC1uZXR3b3JraW5nIGFwcGxpY2F0aW9uIGlzIHZlcnkgcG9wdWxhciwgYnV0IGFzIGl0IHR1cm5zIG91dCBjb21wdXRlcyBmcmllbmRzaGlwIHBhdGhzIHZlcnkgc2xvd2x5LiBJbiBtYW55IGNhc2VzIGhvd2V2ZXIsIHRoZXJlIGRvZXMgbm90IGV2ZW4gZXhpc3QgYSBmcmllbmRzaGlwIHBhdGggYmV0d2VlbiB1c2Vycy4gVGh1cywgTWFyayBoYXMgdGhlIGdyZWF0IGlkZWEgY2hlY2sgaWYgYSBwYXRoIGV4aXN0cywgYmVmb3JlIGFjdHVhbGx5IGNvbXB1dGluZyBpdC4gSGUgXHVmYjAxZ3VyZXMgdGhhdCBjaGVja2luZyBmb3IgdGhlIGV4aXN0ZW5jZSBvZiBhIHBhdGggb25seSBzaG91bGQgYmUgbXVjaCBmYXN0ZXIuIFRoaXMgaXMgd2hlcmUgeW91IGNvbWUgaW4uPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBudW1iZXIgb2YgdXNlcnMsIHRoZSBpbmZvcm1hdGlvbiB3aGljaCB1c2VycyBhcmUgZnJpZW5kcyBhbmQgYSBsaXN0IG9mIHBhaXJzIG9mIHVzZXJzLCB5b3UgYXJlIHRvIGRlY2lkZSBmb3Igd2hpY2ggb2YgdGhvc2UgcGFpcnMgdGhlcmUgYXJlIHBhdGhzIGluIHRoZSBmcmllbmRzaGlwIGdyYXBoLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBudW1iZXIgb2Ygc2NlbmFyaW9zLjxcL3A+XHJcblxyXG48cD5FdmVyeSBzY2VuYXJpbyBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciAxICZsZTsgbiAmbGU7IDEwPHN1cD42PFwvc3VwPiBvZiB1c2VycyBpbiB0aGUgc3lzdGVtLiBUaGUgbnVtYmVyIG9mIGZyaWVuZHNoaXBzIDEgJmxlOyBrICZsZTsgMTA8c3VwPjU8XC9zdXA+IGZvbGxvd3Mgb24gYSBzaW5nbGUgbGluZSwgZm9sbG93ZWQgYnkgayBsaW5lcyB3aXRoIHR3byBudW1iZXJzIDAgJmxlOyBhLCBiICZsdDsgbiBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gRWFjaCBvZiB0aGVzZSBsaW5lcyBkZVx1ZmIwMW5lcyBhIGRpcmVjdCBmcmllbmRzaGlwIHJlbGF0aW9uIGJldHdlZW4gdXNlciBhIGFuZCBiLiBGaW5hbGx5LCB0aGUgbnVtYmVyIG9mIHJlcXVlc3RzIDEgJmxlOyBtICZsZTsgMTA8c3VwPjU8XC9zdXA+IGlzIG9uIGEgc2luZ2xlIGxpbmUsIGZvbGxvd2VkIGJ5IG0gcGFpcnMgb2YgbnVtYmVycyB1LCB2IHNlcGFyYXRlZCBieSBzcGFjZXMuIEVhY2ggb2YgdGhlc2UgcGFpcnMgaXMgYSByZXF1ZXN0IHRvIGRldGVybWluZSBpZiB0aGVyZSBpcyBhIGZyaWVuZHNoaXAgcGF0aCBiZXR3ZWVuIHRoZSB1c2VycyB1IGFuZCB2IGEuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBmb3IgZXZlcnkgc2NlbmFyaW8gYmVnaW5zIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgJmxkcXVvO1NjZW5hcmlvIGk6JnJkcXVvOywgd2hlcmUgaSBpcyB0aGUgbnVtYmVyIG9mIHRoZSBzY2VuYXJpbyBjb3VudGluZyBmcm9tIDEuPFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIHJlcXVlc3QsIHByaW50IGEgc2luZ2xlIGxpbmUgd2l0aCBlaXRoZXIgdGhlIG51bWJlciAxIGlmIHRoZSB0d28gdXNlcnMgaW4gdGhpcyByZXF1ZXN0IGFyZSBjb25uZWN0ZWQsIG9yIDAgb3RoZXJ3aXNlLiBFdmVyeSBzY2VuYXJpbyBpcyBcdWZiMDFuaXNoZWQgYnkgYSBibGFuayBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

접근 방법

- 분리집합을 통해 연결되어있는 집합의 인덱스 번호를 갱신해가며 테스트 케이스별로 출력조건에 맞게 출력한다.

코드

# https://www.acmicpc.net/problem/7511
# 접근 방법
# 분리집합을 통해 연결되어있는 집합의 인덱스 번호를 갱신해가며 테스트 케이스별로 출력조건에 맞게 출력한다.
def get_parent(friend):
    if parent[friend] == friend:
        return friend
    parent[friend] = get_parent(parent[friend]) 
    return parent[friend]

def find_union(friend1, friend2):
    n1 = get_parent(friend1)
    n2 = get_parent(friend2)
    if n1 > n2:
        parent[n1] = n2
    else:
        parent[n2] = n1
    
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
tc = int(input())
for i in range(1, tc+1):
    n, k = int(input()), int(input())
    parent = [j for j in range(n)]
    for _ in range(k):
        a, b = map(int, input().split())
        find_union(a, b)
    print(f'Scenario {i}:')
    m = int(input())
    for _ in range(m):
        u, v = map(int, input().split())
        if get_parent(u) == get_parent(v):
            print(1)
        else:
            print(0)
    print()