시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 86 53 46 66.667%

문제

ACM(Advanced Chip Manufacture)이라는 회사의 수석 칩(chip) 설계자인 한승이는 고민에 빠져있다. 경로 설계자들의 잘못으로 두 개의 블럭의 포트를 연결하는 칩 위의 시그널들이 서로 교차하게 만들어졌다. 이 시점에서 경로 설계를 다시 하는 것은 비용이 너무 많이든다. 그 대신 엔지이너들은 교차하는 시그널들을 브리징 하기로 했다. 브리징은 시그널이 서로 교차하는 경우 하나의 시그널이 다른 시그널과 접촉하지 않도록 수직으로 띄우는 작업이다. 하지만 브리징은 어려운 작업이므로 가능하면 적은 수의 시그널만 브리징 해야한다. 실리콘 표면에서 서로 교차하지 않고 연결될 수 있는 최대 시그널의 개수를 찾는 프로그램을 작성하시오.

 

그림 1. 문제가 생긴 두 개의 블럭의 포트와 포트를 연결하는 시그널 그림 2. 최대 세 개의 시그널이 서로 교차하지 않고 연결될 수 있다. 점선으로 표시된 시그널은 브리징 해야한다.

 

두 개의 블럭의 포트는 1번부터 N번까지 위에서 아래로 번호가 매겨져 있다. 각 포트는 다른 블록의 한 포트와 연결된다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에 포트의 개수 N(1 ≤ N ≤ 40000)이 주어지고, 두 번째 줄부터는 왼쪽 블럭의 포트와 연결되어야 하는 오른쪽 블럭의 포트 번호 ki(1 ≤ ki ≤ N)가 한 줄에 하나씩 N개 주어진다. 즉, i+1번째 줄에는 왼쪽 블럭의 i번 포트와 연결되어야 하는 오른쪽 블럭의 포트 번호가 주어진다.

출력

각 테스트 케이스에 대해 서로 교차하지 않고 연결될 수 있는 최대 시그널의 개수를 한 줄에 하나씩 출력한다.

예제 입력 1

3
6
4
2
6
3
1
5
10
2
3
4
5
6
7
8
9
10
1
9
5
8
9
2
3
1
7
4
6

예제 출력 1

3
9
4
W3sicHJvYmxlbV9pZCI6IjMwNjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlMGNcdWI5YWNcdWM5ZDUgXHVjMmRjXHVhZGY4XHViMTEwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRBQ00oQWR2YW5jZWQgQ2hpcCBNYW51ZmFjdHVyZSlcdWM3NzRcdWI3N2NcdWIyOTQgXHVkNjhjXHVjMGFjXHVjNzU4IFx1YzIxOFx1YzExZCBcdWNlNjkoY2hpcCkgXHVjMTI0XHVhY2M0XHVjNzkwXHVjNzc4IFx1ZDU1Y1x1YzJiOVx1Yzc3NFx1YjI5NCBcdWFjZTBcdWJiZmNcdWM1ZDAgXHViZTYwXHVjODM4XHVjNzg4XHViMmU0LiBcdWFjYmRcdWI4NWMgXHVjMTI0XHVhY2M0XHVjNzkwXHViNGU0XHVjNzU4IFx1Yzc5OFx1YmFiYlx1YzczY1x1Yjg1YyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YmUxNFx1YjdlZFx1Yzc1OCBcdWQzZWNcdWQyYjhcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1Y2U2OSBcdWM3MDRcdWM3NTggXHVjMmRjXHVhZGY4XHViMTEwXHViNGU0XHVjNzc0IFx1YzExY1x1Yjg1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWFjOGMgXHViOWNjXHViNGU0XHVjNWI0XHVjODRjXHViMmU0LiBcdWM3NzQgXHVjMmRjXHVjODEwXHVjNWQwXHVjMTFjIFx1YWNiZFx1Yjg1YyBcdWMxMjRcdWFjYzRcdWI5N2MgXHViMmU0XHVjMmRjIFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHViZTQ0XHVjNmE5XHVjNzc0IFx1YjEwOFx1YmIzNCBcdWI5Y2VcdWM3NzRcdWI0ZTBcdWIyZTQuIFx1YWRmOCBcdWIzMDBcdWMyZTAgXHVjNWQ0XHVjOWMwXHVjNzc0XHViMTA4XHViNGU0XHVjNzQwIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWMyZGNcdWFkZjhcdWIxMTBcdWI0ZTRcdWM3NDQgXHViZTBjXHViOWFjXHVjOWQ1IFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YmUwY1x1YjlhY1x1YzlkNVx1Yzc0MCBcdWMyZGNcdWFkZjhcdWIxMTBcdWM3NzQgXHVjMTFjXHViODVjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzJkY1x1YWRmOFx1YjExMFx1Yzc3NCBcdWIyZTRcdWI5NzggXHVjMmRjXHVhZGY4XHViMTEwXHVhY2ZjIFx1YzgxMVx1Y2QwOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIzYzRcdWI4NWQgXHVjMjE4XHVjOWMxXHVjNzNjXHViODVjIFx1Yjc0NFx1YzZiMFx1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWJlMGNcdWI5YWNcdWM5ZDVcdWM3NDAgXHVjNWI0XHViODI0XHVjNmI0IFx1Yzc5MVx1YzVjNVx1Yzc3NFx1YmJjMFx1Yjg1YyBcdWFjMDBcdWIyYTVcdWQ1NThcdWJhNzQgXHVjODAxXHVjNzQwIFx1YzIxOFx1Yzc1OCBcdWMyZGNcdWFkZjhcdWIxMTBcdWI5Y2MgXHViZTBjXHViOWFjXHVjOWQ1IFx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC4gXHVjMmU0XHViOWFjXHVjZjU4IFx1ZDQ1Y1x1YmE3NFx1YzVkMFx1YzExYyBcdWMxMWNcdWI4NWMgXHVhZDUwXHVjYzI4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWM1ZjBcdWFjYjBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVjMmRjXHVhZGY4XHViMTEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG48cD5cclxuXHQmbmJzcDs8XC9wPlxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NTAlO3RleHQtYWxpZ246Y2VudGVyXCI+XHJcblx0XHRcdFx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaGlwMS5wbmdcIiBzdHlsZT1cIndpZHRoOiAxMzlweDsgaGVpZ2h0OiAxODRweDtcIiBcLz48XC90ZD5cclxuXHRcdFx0PHRkIHN0eWxlPVwid2lkdGg6NTAlO3RleHQtYWxpZ246Y2VudGVyXCI+XHJcblx0XHRcdFx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jaGlwMi5wbmdcIiBzdHlsZT1cIndpZHRoOiAxMzlweDsgaGVpZ2h0OiAxODNweDtcIiBcLz48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlxyXG5cdFx0XHRcdDxzdHJvbmc+XHVhZGY4XHViOWJjIDEuPFwvc3Ryb25nPiBcdWJiMzhcdWM4MWNcdWFjMDAgXHVjMGRkXHVhZTM0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViZTE0XHViN2VkXHVjNzU4IFx1ZDNlY1x1ZDJiOFx1YzY0MCBcdWQzZWNcdWQyYjhcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzJkY1x1YWRmOFx1YjExMDxcL3RkPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlxyXG5cdFx0XHRcdDxzdHJvbmc+XHVhZGY4XHViOWJjIDIuPFwvc3Ryb25nPiBcdWNkNWNcdWIzMDAgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWMyZGNcdWFkZjhcdWIxMTBcdWM3NzQgXHVjMTFjXHViODVjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFjZTAgXHVjNWYwXHVhY2IwXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzgxMFx1YzEyMFx1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MWMgXHVjMmRjXHVhZGY4XHViMTEwXHVjNzQwIFx1YmUwY1x1YjlhY1x1YzlkNSBcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcbjxwPlxyXG5cdCZuYnNwOzxcL3A+XHJcbjxwPlxyXG5cdFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViZTE0XHViN2VkXHVjNzU4IFx1ZDNlY1x1ZDJiOFx1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzU0NFx1Yjc5OFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDNlY1x1ZDJiOFx1YjI5NCBcdWIyZTRcdWI5NzggXHViZTE0XHViODVkXHVjNzU4IFx1ZDU1YyBcdWQzZWNcdWQyYjhcdWM2NDAgXHVjNWYwXHVhY2IwXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDNlY1x1ZDJiOFx1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsZTsgTiAmbGU7IDQwMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwXHViMjk0IFx1YzY3Y1x1Y2FiZCBcdWJlMTRcdWI3ZWRcdWM3NTggXHVkM2VjXHVkMmI4XHVjNjQwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YmUxNFx1YjdlZFx1Yzc1OCBcdWQzZWNcdWQyYjggXHViYzg4XHVkNjM4IGs8c3ViPmk8XC9zdWI+KDEgJmxlOyBrPHN1Yj5pPFwvc3ViPiAmbGU7IE4pXHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IE5cdWFjMWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5ODksIGkrMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNjdjXHVjYWJkIFx1YmUxNFx1YjdlZFx1Yzc1OCBpXHViYzg4IFx1ZDNlY1x1ZDJiOFx1YzY0MCBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWJlMTRcdWI3ZWRcdWM3NTggXHVkM2VjXHVkMmI4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzExY1x1Yjg1YyBcdWFkNTBcdWNjMjhcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YzVmMFx1YWNiMFx1YjQyMCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWMyZGNcdWFkZjhcdWIxMTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDY2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnJpZGdpbmcgc2lnbmFscyIsImRlc2NyaXB0aW9uIjoiPHA+JiMzOTtPaCBubywgdGhleSYjMzk7dmUgZG9uZSBpdCBhZ2FpbiYjMzk7LCBjcmllcyB0aGUgY2hpZWYgZGVzaWduZXIgYXQgdGhlIFdhZmVybGFuZCBjaGlwIGZhY3RvcnkuIE9uY2UgbW9yZSB0aGUgcm91dGluZyBkZXNpZ25lcnMgaGF2ZSBzY3Jld2VkIHVwIGNvbXBsZXRlbHksIG1ha2luZyB0aGUgc2lnbmFscyBvbiB0aGUgY2hpcCBjb25uZWN0aW5nIHRoZSBwb3J0cyBvZiB0d28gZnVuY3Rpb25hbCBibG9ja3MgY3Jvc3MgZWFjaCBvdGhlciBhbGwgb3ZlciB0aGUgcGxhY2UuIEF0IHRoaXMgbGF0ZSBzdGFnZSBvZiB0aGUgcHJvY2VzcywgaXQgaXMgdG9vIGV4cGVuc2l2ZSB0byByZWRvIHRoZSByb3V0aW5nLiBJbnN0ZWFkLCB0aGUgZW5naW5lZXJzIGhhdmUgdG8gYnJpZGdlIHRoZSBzaWduYWxzLCB1c2luZyB0aGUgdGhpcmQgZGltZW5zaW9uLCBzbyB0aGF0IG5vIHR3byBzaWduYWxzIGNyb3NzLiBIb3dldmVyLCBicmlkZ2luZyBpcyBhIGNvbXBsaWNhdGVkIG9wZXJhdGlvbiwgYW5kIHRodXMgaXQgaXMgZGVzaXJhYmxlIHRvIGJyaWRnZSBhcyBmZXcgc2lnbmFscyBhcyBwb3NzaWJsZS4gVGhlIGNhbGwgZm9yIGEgY29tcHV0ZXIgcHJvZ3JhbSB0aGF0IGZpbmRzIHRoZSBtYXhpbXVtIG51bWJlciBvZiBzaWduYWxzIHdoaWNoIG1heSBiZSBjb25uZWN0ZWQgb24gdGhlIHNpbGljb24gc3VyZmFjZSB3aXRob3V0IGNyb3NzaW5nIGVhY2ggb3RoZXIsIGlzIGltbWluZW50LiBCZWFyaW5nIGluIG1pbmQgdGhhdCB0aGVyZSBtYXkgYmUgdGhvdXNhbmRzIG9mIHNpZ25hbCBwb3J0cyBhdCB0aGUgYm91bmRhcnkgb2YgYSBmdW5jdGlvbmFsIGJsb2NrLCB0aGUgcHJvYmxlbSBhc2tzIHF1aXRlIGEgbG90IG9mIHRoZSBwcm9ncmFtbWVyLiBBcmUgeW91IHVwIHRvIHRoZSB0YXNrPzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JyaWRpbmdzaWduYWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjI1cHg7IHdpZHRoOjUzMnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxLiBUbyB0aGUgbGVmdDogVGhlIHR3byBibG9ja3MmIzM5OyBwb3J0cyBhbmQgdGhlaXIgc2lnbmFsIG1hcHBpbmcgKDQsMiw2LDMsMSw1KS4gVG8gdGhlIHJpZ2h0OiBBdCBtb3N0IHRocmVlIHNpZ25hbHMgbWF5IGJlIHJvdXRlZCBvbiB0aGUgc2lsaWNvbiBzdXJmYWNlIHdpdGhvdXQgY3Jvc3NpbmcgZWFjaCBvdGhlci4gVGhlIGRhc2hlZCBzaWduYWxzIG11c3QgYmUgYnJpZGdlZC48XC9wPlxyXG5cclxuPHA+QSB0eXBpY2FsIHNpdHVhdGlvbiBpcyBzY2hlbWF0aWNhbGx5IGRlcGljdGVkIGluIGZpZ3VyZSAxLiBUaGUgcG9ydHMgb2YgdGhlIHR3byBmdW5jdGlvbmFsIGJsb2NrcyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIHAsIGZyb20gdG9wIHRvIGJvdHRvbS4gVGhlIHNpZ25hbCBtYXBwaW5nIGlzIGRlc2NyaWJlZCBieSBhIHBlcm11dGF0aW9uIG9mIHRoZSBudW1iZXJzIDEgdG8gcCBpbiB0aGUgZm9ybSBvZiBhIGxpc3Qgb2YgcCB1bmlxdWUgbnVtYmVycyBpbiB0aGUgcmFuZ2UgMSB0byBwLCBpbiB3aGljaCB0aGUgaTp0aCBudW1iZXIgc3BlY2lmaWVzIHdoaWNoIHBvcnQgb24gdGhlIHJpZ2h0IHNpZGUgc2hvdWxkIGJlIGNvbm5lY3RlZCB0byB0aGUgaTp0aCBwb3J0IG9uIHRoZSBsZWZ0IHNpZGUuIFR3byBzaWduYWxzIGNyb3NzIGlmIGFuZCBvbmx5IGlmIHRoZSBzdHJhaWdodCBsaW5lcyBjb25uZWN0aW5nIHRoZSB0d28gcG9ydHMgb2YgZWFjaCBwYWlyIGRvLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LCB0aGVyZSBpcyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHRlbGxpbmcgdGhlIG51bWJlciBvZiB0ZXN0IHNjZW5hcmlvcyB0byBmb2xsb3cuIEVhY2ggdGVzdCBzY2VuYXJpbyBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIHAmbHQ7NDAwMDAsIHRoZSBudW1iZXIgb2YgcG9ydHMgb24gdGhlIHR3byBmdW5jdGlvbmFsIGJsb2Nrcy4gVGhlbiBmb2xsb3cgcCBsaW5lcywgZGVzY3JpYmluZyB0aGUgc2lnbmFsIG1hcHBpbmc6IE9uIHRoZSBpOnRoIGxpbmUgaXMgdGhlIHBvcnQgbnVtYmVyIG9mIHRoZSBibG9jayBvbiB0aGUgcmlnaHQgc2lkZSB3aGljaCBzaG91bGQgYmUgY29ubmVjdGVkIHRvIHRoZSBpOnRoIHBvcnQgb2YgdGhlIGJsb2NrIG9uIHRoZSBsZWZ0IHNpZGUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBzY2VuYXJpbywgb3V0cHV0IG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1heGltdW0gbnVtYmVyIG9mIHNpZ25hbHMgd2hpY2ggbWF5IGJlIHJvdXRlZCBvbiB0aGUgc2lsaWNvbiBzdXJmYWNlIHdpdGhvdXQgY3Jvc3NpbmcgZWFjaCBvdGhlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=