시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 109 14 7 12.963%

문제

암호기법 덕분에 우리는 의도된 수신자 이외에 누구도 메세지를 읽을 수 없도록 암호화 할 수 있다. 하지만, 암호화된 메세지들은 실제로 수신자에게 도달하지 않을 경우 쓸모가 없다. 오늘날, 컴퓨터 네트워크는 이러한 메세지들을 전송하는 가장 일반적인 방법이다. 이 문제에서는 네트워크 공급자들이 해결해야 하는 문제에 대해 공부한다. 메세지는 암호화되어있기 때문에, 네트워크 보안에 대해 더이상 신경쓰지 않아도 됨을 기억해라.

컴퓨터(서버)를 연결하는 네트워크 케이블들은 다른 회사에 속해 있다. 새로 만들어진 독점 금지법은 모든 회사가 각 서버에서 케이블을 2개보다 많이 소유하지 못하게 한다. 또한, 자원 낭비를 피하기 위해 각 회사가 불필요한 케이블을 소유하면 안 된다는 내용도 있다. (즉, 어떠한 케이블을 제거하면 이전에 연결되어있던 두 개의 서버는 연결이 끊어진다.)  회사들은 케이블을 계속 사고 팔기 때문에, 이러한 규정을 시행하는 것은 매우 어렵다. 당신의 임무는 이러한 규정의 시행을 도와주는 프로그램을 작성하는 것이다!

입력

입력은 몇 가지 예시를 포함한다. 각 예시의 첫 번째 줄에는 공백으로 구분된 네 개의 정수 N, M, C, T가 주어진다. N은 서버의 개수(1<=N<=8000), M은 케이블의 개수(0<=M<=100 000), C는 회사의 개수(1<=C<=100), T는 케이블 판매 거래수(0<=T<=100 000)를 나타낸다.

다음의 M행은 케이블에 대한 내용이다. 각 줄에는 공백으로 구분된 세개의 정수 Sj1, Sj2, Kj가 주어진다. Sj1과 Sj2는 해당 케이블로 연결된 서버의 번호이고(1<=Sj1<Sj2<=n), Kj는 처음 케이블을 소유하고 있는 회사의 번호이다. 각 서버 쌍에는 최대 하나의 케이블만 연결된다. 초기 상태는 규정을 만족한다. 즉, 각 회사는 각 서버에 최대 2개의 케이블을 소유하고 있으며, 한 회사가 소유한 케이블 시스템에는 사이클이 없다.

마지막으로 다음의 T행에는 정수 Si1, Si2, Ki가 주어진다. 하나의 거래에 대해 Ki (1<=Ki<=C) 회사가 서버 Si1와 Si2 사이의 케이블을 구매하려는 것을 나타낸다.

마지막 예시의 다음에는 4개의 0이 주어진다.

출력

각각의 예시에 대해, 거래의 결과를 나타내는 T개의 행을 출력하라. 가능한 출력결과는 다음과 같다.

  • "No such cable." : 서버 쌍이 케이블로 연결되지 않을 때
  • "Already owned." : 이미 회사 Ki가 케이블을 가지고 있을 때
  • "Forbidden: monopoly." : 회사 Ki가 이미 서버 Si1이나 Si2에서 2개의 케이블을 가지고 있을 때
  • "Forbidden: redundant." : 회사 Ki가 서버 Si1과 Si2에 대해 각각 최대 1개의 케이블을 가지고 있으나 소유권을 부여할 경우 Ki가 가진 케이블이 사이클을 형성할 때
  • "Sold." : 위의 제한 사항 중 하나도 적용되지 않을 때. 이 경우 서버 Si1과 Si2에 대한 케이블의 소유권은 이후 거래를 위해 Ki에게 옮겨간다.
각 인스턴스 뒤에는 한 개의 빈 줄을 출력해라.

예제 입력 1

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

예제 출력 1

Sold.
Already owned.
Forbidden: monopoly.
Forbidden: redundant.
No such cable.

Already owned.
W3sicHJvYmxlbV9pZCI6IjM0MjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWMwYzFcdWQ1NWMgXHVhZGRjXHVjODE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1NTRcdWQ2MzhcdWFlMzBcdWJjOTUgXHViMzU1XHViZDg0XHVjNWQwIFx1YzZiMFx1YjlhY1x1YjI5NCBcdWM3NThcdWIzYzRcdWI0MWMgXHVjMjE4XHVjMmUwXHVjNzkwIFx1Yzc3NFx1YzY3OFx1YzVkMCBcdWIyMDRcdWFkNmNcdWIzYzQgXHViYTU0XHVjMTM4XHVjOWMwXHViOTdjIFx1Yzc3ZFx1Yzc0NCBcdWMyMTggXHVjNWM2XHViM2M0XHViODVkIFx1YzU1NFx1ZDYzOFx1ZDY1NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWM1NTRcdWQ2MzhcdWQ2NTRcdWI0MWMgXHViYTU0XHVjMTM4XHVjOWMwXHViNGU0XHVjNzQwIFx1YzJlNFx1YzgxY1x1Yjg1YyBcdWMyMThcdWMyZTBcdWM3OTBcdWM1ZDBcdWFjOGMgXHViM2M0XHViMmVjXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWFjYmRcdWM2YjAgXHVjNGY4XHViYWE4XHVhYzAwIFx1YzVjNlx1YjJlNC4gXHVjNjI0XHViMjk4XHViMGEwLCBcdWNlZjRcdWQ0ZThcdWQxMzAgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHViMjk0IFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWJhNTRcdWMxMzhcdWM5YzBcdWI0ZTRcdWM3NDQgXHVjODA0XHVjMWExXHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3N2NcdWJjMThcdWM4MDFcdWM3NzggXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjXHViMjk0IFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyBcdWFjZjVcdWFlMDlcdWM3OTBcdWI0ZTRcdWM3NzQgXHVkNTc0XHVhY2IwXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWJiMzhcdWM4MWNcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWNmNVx1YmQ4MFx1ZDU1Y1x1YjJlNC4gXHViYTU0XHVjMTM4XHVjOWMwXHViMjk0IFx1YzU1NFx1ZDYzOFx1ZDY1NFx1YjQxOFx1YzViNFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YjEyNFx1ZDJiOFx1YzZjY1x1ZDA2YyBcdWJjZjRcdWM1NDhcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWMyZTBcdWFjYmRcdWM0ZjBcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQyOFx1Yzc0NCBcdWFlMzBcdWM1YjVcdWQ1NzRcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlx1Y2VmNFx1ZDRlOFx1ZDEzMChcdWMxMWNcdWJjODQpXHViOTdjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmMgXHVjZjAwXHVjNzc0XHViZTE0XHViNGU0XHVjNzQwIFx1YjJlNFx1Yjk3OCBcdWQ2OGNcdWMwYWNcdWM1ZDAgXHVjMThkXHVkNTc0IFx1Yzc4OFx1YjJlNC4gXHVjMGM4XHViODVjIFx1YjljY1x1YjRlNFx1YzViNFx1YzljNCBcdWIzYzVcdWM4MTAgXHVhZTA4XHVjOWMwXHViYzk1XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVhYzAxIFx1YzExY1x1YmM4NFx1YzVkMFx1YzExYyBcdWNmMDBcdWM3NzRcdWJlMTRcdWM3NDQgMlx1YWMxY1x1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NzQgXHVjMThjXHVjNzIwXHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWM4YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMFx1ZDU1YywgXHVjNzkwXHVjNmQwIFx1YjBhZFx1YmU0NFx1Yjk3YyBcdWQ1M2NcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWMwMSBcdWQ2OGNcdWMwYWNcdWFjMDAgXHViZDg4XHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2YwMFx1Yzc3NFx1YmUxNFx1Yzc0NCBcdWMxOGNcdWM3MjBcdWQ1NThcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNFx1YjI5NCBcdWIwYjRcdWM2YTlcdWIzYzQgXHVjNzg4XHViMmU0LiAoXHVjOTg5LCBcdWM1YjRcdWI1YTBcdWQ1NWMgXHVjZjAwXHVjNzc0XHViZTE0XHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU1OFx1YmE3NCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0XHVjNzg4XHViMzU4IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjMTFjXHViYzg0XHViMjk0IFx1YzVmMFx1YWNiMFx1Yzc3NCBcdWIwNGFcdWM1YjRcdWM5YzRcdWIyZTQuKSAmbmJzcDtcdWQ2OGNcdWMwYWNcdWI0ZTRcdWM3NDAgXHVjZjAwXHVjNzc0XHViZTE0XHVjNzQ0IFx1YWNjNFx1YzE4ZCBcdWMwYWNcdWFjZTAgXHVkMzE0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzc0XHViN2VjXHVkNTVjIFx1YWRkY1x1YzgxNVx1Yzc0NCBcdWMyZGNcdWQ1ODlcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MzVcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWM3ODRcdWJiMzRcdWIyOTQgXHVjNzc0XHViN2VjXHVkNTVjIFx1YWRkY1x1YzgxNVx1Yzc1OCBcdWMyZGNcdWQ1ODlcdWM3NDQgXHViM2M0XHVjNjQwXHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0ITxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YmE4NyBcdWFjMDBcdWM5YzAgXHVjNjA4XHVjMmRjXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YzYwOFx1YzJkY1x1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjIFx1YjEyNCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IE4sIE0sIEMsIFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIFx1YzExY1x1YmM4NFx1Yzc1OCBcdWFjMWNcdWMyMTgoMSZsdDs9TiZsdDs9ODAwMCksIE1cdWM3NDAgXHVjZjAwXHVjNzc0XHViZTE0XHVjNzU4IFx1YWMxY1x1YzIxOCgwJmx0Oz1NJmx0Oz0xMDAgMDAwKSwgQ1x1YjI5NCBcdWQ2OGNcdWMwYWNcdWM3NTggXHVhYzFjXHVjMjE4KDEmbHQ7PUMmbHQ7PTEwMCksIFRcdWIyOTQgXHVjZjAwXHVjNzc0XHViZTE0IFx1ZDMxMFx1YjllNCBcdWFjNzBcdWI3OThcdWMyMTgoMCZsdDs9VCZsdDs9MTAwIDAwMClcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGNcdWM3NTggTVx1ZDU4OVx1Yzc0MCBcdWNmMDBcdWM3NzRcdWJlMTRcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjBiNFx1YzZhOVx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjIFx1YzEzOFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggUzxzdWI+ajE8XC9zdWI+LCBTPHN1Yj5qMjxcL3N1Yj4sIEs8c3ViPmo8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gUzxzdWI+ajE8XC9zdWI+XHVhY2ZjIFM8c3ViPmoyPFwvc3ViPlx1YjI5NCBcdWQ1NzRcdWIyZjkgXHVjZjAwXHVjNzc0XHViZTE0XHViODVjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWMxMWNcdWJjODRcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHVhY2UwKDEmbHQ7PVM8c3ViPmoxPFwvc3ViPiZsdDtTPHN1Yj5qMjxcL3N1Yj4mbHQ7PW4pLCBLPHN1Yj5qPFwvc3ViPlx1YjI5NCBcdWNjOThcdWM3NGMgXHVjZjAwXHVjNzc0XHViZTE0XHVjNzQ0IFx1YzE4Y1x1YzcyMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVkNjhjXHVjMGFjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzExY1x1YmM4NCBcdWMzMGRcdWM1ZDBcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWNmMDBcdWM3NzRcdWJlMTRcdWI5Y2MgXHVjNWYwXHVhY2IwXHViNDFjXHViMmU0LiBcdWNkMDhcdWFlMzAgXHVjMGMxXHVkMGRjXHViMjk0IFx1YWRkY1x1YzgxNVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuIFx1Yzk4OSwgXHVhYzAxIFx1ZDY4Y1x1YzBhY1x1YjI5NCBcdWFjMDEgXHVjMTFjXHViYzg0XHVjNWQwIFx1Y2Q1Y1x1YjMwMCAyXHVhYzFjXHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YmUxNFx1Yzc0NCBcdWMxOGNcdWM3MjBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQ1NWMgXHVkNjhjXHVjMGFjXHVhYzAwIFx1YzE4Y1x1YzcyMFx1ZDU1YyBcdWNmMDBcdWM3NzRcdWJlMTQgXHVjMmRjXHVjMmE0XHVkMTVjXHVjNWQwXHViMjk0IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyBcdWIyZTRcdWM3NGNcdWM3NTggVFx1ZDU4OVx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggUzxzdWI+aTE8XC9zdWI+LCBTPHN1Yj5pMjxcL3N1Yj4sIEs8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTU4XHViMDk4XHVjNzU4IFx1YWM3MFx1Yjc5OFx1YzVkMCBcdWIzMDBcdWQ1NzQgSzxzdWI+aTxcL3N1Yj4gKDEmbHQ7PUs8c3ViPmk8XC9zdWI+Jmx0Oz1DKSBcdWQ2OGNcdWMwYWNcdWFjMDAgXHVjMTFjXHViYzg0IFM8c3ViPmkxPFwvc3ViPlx1YzY0MCBTPHN1Yj5pMjxcL3N1Yj4gXHVjMGFjXHVjNzc0XHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YmUxNFx1Yzc0NCBcdWFkNmNcdWI5ZTRcdWQ1NThcdWI4MjRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1YzYwOFx1YzJkY1x1Yzc1OCBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgNFx1YWMxY1x1Yzc1OCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjNjA4XHVjMmRjXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVhYzcwXHViNzk4XHVjNzU4IFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgVFx1YWMxY1x1Yzc1OCBcdWQ1ODlcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLiBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDljXHViODI1XHVhY2IwXHVhY2ZjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+JnF1b3Q7Tm8gc3VjaCBjYWJsZS4mcXVvdDsgOiBcdWMxMWNcdWJjODQgXHVjMzBkXHVjNzc0IFx1Y2YwMFx1Yzc3NFx1YmUxNFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YjU0YzxcL2xpPlxyXG5cdDxsaT4mcXVvdDtBbHJlYWR5IG93bmVkLiZxdW90OyA6IFx1Yzc3NFx1YmJmOCBcdWQ2OGNcdWMwYWMgSzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjZjAwXHVjNzc0XHViZTE0XHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWM3ODhcdWM3NDQgXHViNTRjPFwvbGk+XHJcblx0PGxpPiZxdW90O0ZvcmJpZGRlbjogbW9ub3BvbHkuJnF1b3Q7IDogXHVkNjhjXHVjMGFjIEs8c3ViPmk8XC9zdWI+XHVhYzAwIFx1Yzc3NFx1YmJmOCBcdWMxMWNcdWJjODQgUzxzdWI+aTE8XC9zdWI+XHVjNzc0XHViMDk4IFM8c3ViPmkyPFwvc3ViPlx1YzVkMFx1YzExYyAyXHVhYzFjXHVjNzU4IFx1Y2YwMFx1Yzc3NFx1YmUxNFx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVjNzQ0IFx1YjU0YzxcL2xpPlxyXG5cdDxsaT4mcXVvdDtGb3JiaWRkZW46IHJlZHVuZGFudC4mcXVvdDsgOiBcdWQ2OGNcdWMwYWMgSzxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjMTFjXHViYzg0IFM8c3ViPmkxPFwvc3ViPlx1YWNmYyBTPHN1Yj5pMjxcL3N1Yj5cdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWMwMVx1YWMwMSBcdWNkNWNcdWIzMDAgMVx1YWMxY1x1Yzc1OCBcdWNmMDBcdWM3NzRcdWJlMTRcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YzczY1x1YjA5OCBcdWMxOGNcdWM3MjBcdWFkOGNcdWM3NDQgXHViZDgwXHVjNWVjXHVkNTYwIFx1YWNiZFx1YzZiMCBLPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWFjMDBcdWM5YzQgXHVjZjAwXHVjNzc0XHViZTE0XHVjNzc0IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc0NCBcdWQ2MTVcdWMxMzFcdWQ1NjAgXHViNTRjPFwvbGk+XHJcblx0PGxpPiZxdW90O1NvbGQuJnF1b3Q7IDogXHVjNzA0XHVjNzU4IFx1YzgxY1x1ZDU1YyBcdWMwYWNcdWQ1NmQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjNjNCBcdWM4MDFcdWM2YTlcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YjU0Yy4gXHVjNzc0IFx1YWNiZFx1YzZiMCBcdWMxMWNcdWJjODQgUzxzdWI+aTE8XC9zdWI+XHVhY2ZjIFM8c3ViPmkyPFwvc3ViPlx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjZjAwXHVjNzc0XHViZTE0XHVjNzU4IFx1YzE4Y1x1YzcyMFx1YWQ4Y1x1Yzc0MCBcdWM3NzRcdWQ2YzQgXHVhYzcwXHViNzk4XHViOTdjIFx1YzcwNFx1ZDU3NCBLPHN1Yj5pPFwvc3ViPlx1YzVkMFx1YWM4YyBcdWM2MmVcdWFjYThcdWFjMDRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPGRpdj5cdWFjMDEgXHVjNzc4XHVjMmE0XHVkMTM0XHVjMmE0IFx1YjRhNFx1YzVkMFx1YjI5NCBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHViNzdjLjxcL2Rpdj5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzQyMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN0cmFuZ2UgUmVndWxhdGlvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoYW5rIHRvIGNyeXB0b2dyYXBoeSwgd2UgYXJlIGFibGUgdG8gZW5jcnlwdCBtZXNzYWdlcyBzdWNoIHRoYXQgbm9vbmUgKGV4Y2VwdCB0aGUgaW50ZW5kZWQgcmVjaXBpZW50KSBpcyBhYmxlIHRvIHJlYWQgdGhlbS4gSG93ZXZlciwgZW5jcnlwdGVkIG1lc3NhZ2VzIGFyZSBvZiBubyB1c2UgaWYgdGhleSBkbyBub3QgYWN0dWFsbHkgcmVhY2ggdGhlIHJlY2lwaWVudC4gVGhlc2UgZGF5cywgY29tcHV0ZXIgbmV0d29yayBpcyB0aGUgbW9zdCB0eXBpY2FsIG1lYW4gdG8gc2VuZCBzdWNoIG1lc3NhZ2VzLiBJbiB0aGlzIHByb2JsZW0sIHdlIHdpbGwgc3R1ZHkgdGhlIGlzc3VlcyB0aGUgbmV0d29ya2luZyBwcm92aWRlcnMgaGF2ZSB0byBzb2x2ZS4gQW5kIHJlbWVtYmVyOiBzaW5jZSB0aGUgbWVzc2FnZSBpcyBlbmNyeXB0ZWQsIHdlIGRvIG5vdCBuZWVkIHRvIGNhcmUgYWJvdXQgdGhlIG5ldHdvcmsgcHJpdmFjeSBhbnltb3JlLjxcL3A+XHJcblxyXG48cD5UaGUgbmV0d29yayBjYWJsZXMgam9pbmluZyBjb21wdXRlcnMgKHNlcnZlcnMpIGJlbG9uZyB0byBkaWZmZXJlbnQgY29tcGFuaWVzLiBBIG5ldyBhbnRpbW9ub3BvbHkgbGVnaXNsYXRpb24gcHJldmVudHMgYW55IGNvbXBhbnkgZnJvbSBvd25pbmcgbW9yZSB0aGFuIHR3byBjYWJsZXMgZnJvbSBlYWNoIHNlcnZlci4gRnVydGhlcm1vcmUsIHRvIGF2b2lkIHdhc3RpbmcgcmVzb3VyY2VzLCB0aGVyZSBpcyBhbHNvIGEgbGF3IHNwZWNpZnlpbmcgdGhhdCB0aGUgY2FibGUgc3lzdGVtIG93bmVkIGJ5IGFueSBzaW5nbGUgY29tcGFueSBjYW5ub3QgYmUgcmVkdW5kYW50LCBpLmUuLCByZW1vdmFsIG9mIGFueSBvZiB0aGUgY2FibGVzIHdpbGwgZGlzY29ubmVjdCBzb21lIHR3byBwcmV2aW91c2x5IGNvbm5lY3RlZCBzZXJ2ZXJzLiBTaW5jZSB0aGUgY29tcGFuaWVzIGJ1eSBhbmQgc2VsbCB0aGUgY2FibGVzIGFsbCB0aGUgdGltZSwgaXQgaXMgcXVpdGUgZGlmZmljdWx0IHRvIGVuZm9yY2UgdGhlc2UgcmVndWxhdGlvbnMuIFlvdXIgdGFzayBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBkb2VzIHNvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIHNldmVyYWwgaW5zdGFuY2VzLiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIGluc3RhbmNlIGNvbnRhaW5zIGZvdXIgaW50ZWdlcnMgTiwgTSwgQyBhbmQgVCBzZXBhcmF0ZWQgYnkgc3BhY2VzICZtZGFzaDsgdGhlIG51bWJlciBvZiBzZXJ2ZXJzICgxICZsZTsgTiAmbGU7IDggMDAwKSwgdGhlIG51bWJlciBvZiBjYWJsZXMgKDAgJmxlOyBNICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgY29tcGFuaWVzICgxICZsZTsgQyAmbGU7IDEwMCksIGFuZCB0aGUgbnVtYmVyIG9mIGNhYmxlLXNlbGxpbmcgdHJhbnNhY3Rpb25zICgwICZsZTsgVCAmbGU7IDEwMCAwMDApLCByZXNwZWN0aXZlbHkuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgTSBsaW5lcyBkZXNjcmliZSB0aGUgY2FibGVzLiBFYWNoIG9mIHRoZW0gY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgUzxzdWI+ajE8XC9zdWI+LCBTPHN1Yj5qMjxcL3N1Yj4gYW5kIEs8c3ViPmo8XC9zdWI+ICwgc2VwYXJhdGVkIGJ5IHNwYWNlcywgZ2l2aW5nIHRoZSBudW1iZXJzIG9mIHRoZSBzZXJ2ZXJzIFM8c3ViPmoxPFwvc3ViPiBhbmQgUzxzdWI+ajI8XC9zdWI+ICgxICZsZTsgUzxzdWI+ajE8XC9zdWI+ICZsdDsgUzxzdWI+ajI8XC9zdWI+ICZsZTsgbikgam9pbmVkIGJ5IHRoYXQgY2FibGUgYW5kIHRoZSBudW1iZXIgb2YgdGhlIGNvbXBhbnkgSzxzdWI+ajxcL3N1Yj4gKDEgJmxlOyBLPHN1Yj5qPFwvc3ViPiAmbGU7IEMpIGluaXRpYWxseSBvd25pbmcgdGhlIGNhYmxlLiBGb3IgZWFjaCBwYWlyIG9mIHNlcnZlcnMsIHRoZXJlIGlzIGF0IG1vc3Qgb25lIGNhYmxlIGpvaW5pbmcgdGhlbS4gVGhlIGluaXRpYWwgc3RhdGUgc2F0aXNmaWVzIHRoZSByZWd1bGF0aW9ucywgaS5lLiwgZWFjaCBjb21wYW55IG93bnMgYXQgbW9zdCB0d28gY2FibGVzIGluY2lkZW50IHdpdGggZWFjaCBzZXJ2ZXIsIGFuZCB0aGUgc3lzdGVtIG9mIGNhYmxlcyBvd25lZCBieSBhIHNpbmdsZSBjb21wYW55IGhhcyBubyBjeWNsZXMuPFwvcD5cclxuXHJcbjxwPkZpbmFsbHksIGVhY2ggb2YgdGhlIG5leHQgVCBsaW5lcyBjb250YWlucyBpbnRlZ2VycyBTPHN1Yj5pMTxcL3N1Yj4sIFM8c3ViPmkyPFwvc3ViPiBhbmQgSzxzdWI+aTxcL3N1Yj4gZGVzY3JpYmluZyBvbmUgdHJhbnNhY3Rpb24gaW4gd2hpY2ggdGhlIGNvbXBhbnkgSzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBLaSAmbGU7IEMpIHRyaWVzIHRvIGJ1eSBhIGNhYmxlIGJldHdlZW4gc2VydmVycyBTPHN1Yj5pMTxcL3N1Yj4gYW5kIFM8c3ViPmkyPFwvc3ViPiAoMSAmbGU7IFM8c3ViPmkxPFwvc3ViPiAmbHQ7IFM8c3ViPmkyPFwvc3ViPiAmbGU7IE4pLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBpbnN0YW5jZSBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyBmb3VyIHplcm9zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGlucHV0IGluc3RhbmNlLCBvdXRwdXQgVCBsaW5lcyBkZXNjcmliaW5nIHRoZSBvdXRjb21lIG9mIHRoZSB0cmFuc2FjdGlvbnMuIFRoZSBwb3NzaWJsZSBvdXRjb21lcyBhcmU8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4mbGRxdW87Tm8gc3VjaCBjYWJsZS4mcmRxdW87IGlmIHRoZSBwYWlyIG9mIHNlcnZlcnMgaXMgbm90IGpvaW5lZCBieSBhIGNhYmxlLDxcL2xpPlxyXG5cdDxsaT4mbGRxdW87QWxyZWFkeSBvd25lZC4mcmRxdW87IGlmIHRoZSBjYWJsZSBpcyBhbHJlYWR5IG93bmVkIGJ5IHRoZSBjb21wYW55IEs8c3ViPmk8XC9zdWI+LDxcL2xpPlxyXG5cdDxsaT4mbGRxdW87Rm9yYmlkZGVuOiBtb25vcG9seS4mcmRxdW87IGlmIHRoZSBjb21wYW55IEs8c3ViPmk8XC9zdWI+IGFscmVhZHkgb3ducyB0d28gY2FibGVzIGF0IFM8c3ViPmkxPFwvc3ViPiBvciBTPHN1Yj5pMjxcL3N1Yj4sPFwvbGk+XHJcblx0PGxpPiZsZHF1bztGb3JiaWRkZW46IHJlZHVuZGFudC4mcmRxdW87IGlmIEs8c3ViPmk8XC9zdWI+IG93bnMgYXQgbW9zdCBvbmUgY2FibGUgYXQgZWFjaCBvZiBTPHN1Yj5pMTxcL3N1Yj4gYW5kIFM8c3ViPmkyPFwvc3ViPiwgYnV0IGdyYW50aW5nIHRoZSBvd25lcnNoaXAgd291bGQgY3JlYXRlIGEgY3ljbGUgb2YgY2FibGVzIG93bmVkIGJ5IEs8c3ViPmk8XC9zdWI+LDxcL2xpPlxyXG5cdDxsaT4mbGRxdW87U29sZC4mcmRxdW87IGlmIG5vbmUgb2YgdGhlIGFib3ZlIHJlc3RyaWN0aW9ucyBhcHBseS4gSW4gdGhpcyBjYXNlLCB0aGUgb3duZXJzaGlwIG9mIHRoZSBjYWJsZSBiZXR3ZWVuIFM8c3ViPmkxPFwvc3ViPiBhbmQgUzxzdWI+aTI8XC9zdWI+IGNoYW5nZXMgdG8gSzxzdWI+aTxcL3N1Yj4gZm9yIHRoZSBwdXJwb3NlIG9mIGZ1cnRoZXIgdHJhbnNhY3Rpb25zLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlByaW50IG9uZSBlbXB0eSBsaW5lIGFmdGVyIGVhY2ggaW5zdGFuY2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Europe > Central European Regional Contest > CERC 2011 F번