시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB66000.000%

문제

어랜지는 창영이가 즐겨하는 플래시 게임이다. 이 게임은 1부터 N까지 숫자로 이루어진 순열이 주어졌을 때, 숫자의 위치를 적절히 바꿔서 1,2,3,...,N 순서로 만드는 게임이다.

하지만, 모든 숫자의 위치를 바꿀 수 있는 것은 아니다. 플레이어는 미리 정해져있는 교환만 사용할 수 있다.

창영이는 최고 기록을 깨려고 한다. 따라서, 교환을 되도록 적게 사용하려고 한다.

순열의 순서와 사용할 수 있는 교환의 위치가 주어졌을 때, 교환을 되도록 적게 사용해서 오름차순으로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 순열의 길이 N과 사용할 수 있는 교환의 수 M이 주어진다. (1 ≤ N ≤ 12, 1 ≤ M ≤ N*(N-1)/2)

둘째 줄에는 1부터 N까지 숫자로 이루어져 있는 순열이 주어진다.

셋째 줄부터 M개 줄에는 사용할 수 있는 교환의 방법이 주어진다. 방법은 두 숫자 A와 B로 이루어져 있고, A번째 위치와 B번째 위치의 수를 서로 바꾸는 교환을 사용할 수 있다는 뜻이다. 동일한 교환이 두 개 이상 주어지지 않는다.

출력

첫째 줄에 사용한 교환의 수 X를 출력한다. 다음 줄부터 사용한 교환 번호를 한 줄에 하나씩 출력한다. 입력의 첫 번째로 주어지는 교환이 1번이고, 나머지는 순서대로 증가한다. 항상 답이 존재하는 경우만 입력으로 주어지며, 방법이 여러 가지일 때는 아무거나 출력하면 된다.

예제 입력 1

2 1
2 1
1 2

예제 출력 1

1
1

예제 입력 2

3 2
2 1 3
1 3
2 3

예제 출력 2

3
2
1
2

예제 입력 3

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

예제 출력 3

0
W3sicHJvYmxlbV9pZCI6IjI5MTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJBcnJhbmdlIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI3OWNcdWM5YzBcdWIyOTQgXHVjYzNkXHVjNjAxXHVjNzc0XHVhYzAwIFx1Yzk5MFx1YWNhOFx1ZDU1OFx1YjI5NCBcdWQ1MGNcdWI3OThcdWMyZGMgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMyMmJcdWM3OTBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWJjMTRcdWFmZDRcdWMxMWMgMSwyLDMsLi4uLE4gXHVjMjFjXHVjMTFjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYywgXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViYzE0XHVhZmMwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1YmJmOFx1YjlhYyBcdWM4MTVcdWQ1NzRcdWM4MzhcdWM3ODhcdWIyOTQgXHVhZDUwXHVkNjU4XHViOWNjIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVjZDVjXHVhY2UwIFx1YWUzMFx1Yjg1ZFx1Yzc0NCBcdWFlNjhcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWQ1MFx1ZDY1OFx1Yzc0NCBcdWI0MThcdWIzYzRcdWI4NWQgXHVjODAxXHVhYzhjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxY1x1YzVmNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWM2NDAgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZDUwXHVkNjU4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkNTBcdWQ2NThcdWM3NDQgXHViNDE4XHViM2M0XHViODVkIFx1YzgwMVx1YWM4YyBcdWMwYWNcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyMWNcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IE5cdWFjZmMgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZDUwXHVkNjU4XHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTIsIDEgJmxlOyBNICZsZTsgTiooTi0xKVwvMik8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAxXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjMjJiXHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTRiXHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFkNTBcdWQ2NThcdWM3NTggXHViYzI5XHViYzk1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYzI5XHViYzk1XHVjNzQwIFx1YjQ1MCBcdWMyMmJcdWM3OTAgQVx1YzY0MCBCXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIEFcdWJjODhcdWM5ZjggXHVjNzA0XHVjZTU4XHVjNjQwIEJcdWJjODhcdWM5ZjggXHVjNzA0XHVjZTU4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWMxMWNcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1YWQ1MFx1ZDY1OFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuIFx1YjNkOVx1Yzc3Y1x1ZDU1YyBcdWFkNTBcdWQ2NThcdWM3NzQgXHViNDUwIFx1YWMxYyBcdWM3NzRcdWMwYzEgXHVjOGZjXHVjNWI0XHVjOWMwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFkNTBcdWQ2NThcdWM3NTggXHVjMjE4IFhcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFkNTBcdWQ2NTggXHViYzg4XHVkNjM4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjhcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YWQ1MFx1ZDY1OFx1Yzc3NCAxXHViYzg4XHVjNzc0XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzBcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Yzk5ZFx1YWMwMFx1ZDU1Y1x1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YjJmNVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViOWNjIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YmMyOVx1YmM5NVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzdjIFx1YjU0Y1x1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyOTE4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUE9TTE9aSSIsImRlc2NyaXB0aW9uIjoiPHA+JmxkcXVvO0FycmFuZ2UmcmRxdW87IGlzIGEgcGxhbmV0YXJ5IHBvcHVsYXIgRmxhc2ggZ2FtZS4gSW4gJmxkcXVvO0FycmFuZ2UmcmRxdW87IHRoZSBwbGF5ZXIgaXMgZ2l2ZW4gYSBwZXJtdXRhdGlvbiBvZiBudW1iZXJzIDEgdG8gTiBhbmQgYSBsaXN0IG9mIGFsbG93ZWQgc3dhcHMuIEhlIHRoZW4gaGFzIHRvIHBlcmZvcm0gYSBzZXF1ZW5jZSBvZiBzd2FwcyB0aGF0IHRyYW5zZm9ybXMgdGhlIGluaXRpYWwgcGVybXV0YXRpb24gYmFjayB0byB0aGUgb3JkZXJlZCBzZXF1ZW5jZSAxLDIsMyw0LDUuLi5OLjxcL3A+XHJcblxyXG48cD5JbiBvcmRlciB0byBicmVhayB0aGUgaGlnaCBzY29yZSBsaXN0LCB5b3UgbmVlZCB0byBwZXJmb3JtIHRoZSBtaW5pbWFsIGFtb3VudCBvZiBzd2FwcyBwb3NzaWJsZS4gWW91IGNhbiYjMzk7dCBkbyB0aGF0LCBidXQgeW91IGNhbiB3cml0ZSBhIHByb2dyYW0gdGhhdCBkb2VzIGl0IGZvciB5b3UhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMsIE4gKDEgJmxlOyBOICZsZTsgMTIpLCB0aGUgbGVuZ3RoIG9mIHRoZSBpbml0aWFsIHNlcXVlbmNlIGFuZCBNICgxICZsZTsgTSAmbGU7IE4qKE4gJm5kYXNoOyAxKSBcLyAyKSBudW1iZXIgb2YgYWxsb3dlZCBzd2Fwcy48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgcGVybXV0YXRpb24gb2YgbnVtYmVyIDEgdG8gTi48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTSBsaW5lcyBjb250YWluIGRlc2NyaXB0aW9ucyBvZiBhbGxvd2VkIHN3YXBzLiBJZiB0aGUgbGluZSBjb250YWlucyBudW1iZXJzIEEgYW5kIEIgeW91IGFyZSBhbGxvd2VkIHRvIHN3YXAgdGhlIEEtdGggbnVtYmVyIHdpdGggdGhlIEItdGggbnVtYmVyLiBUaGUgaW5wdXQgd2lsbCBuZXZlciBjb250YWluIHR3byBpZGVudGljYWwgc3dhcHMuPFwvcD5cclxuXHJcbjxwPk5vdGU6IHRoZSB0ZXN0IGRhdGEgc2hhbGwgYmUgc3VjaCB0aGF0IHRoZSBzb2x1dGlvbiwgbm90IG5lY2Vzc2FyaWx5IHVuaXF1ZSwgd2lsbCBhbHdheXMgZXhpc3QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gdGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgcHJpbnQgdGhlIG1pbmltYWwgbnVtYmVyIG9mIHN3YXBzLCBYLiBJbiB0aGUgbmV4dCBYIGxpbmVzIHByaW50IHRoZSByZXF1aXJlZCBzd2FwcywgaW4gb3JkZXIuIEluIGVhY2ggbGluZSBwcmludCB0aGUgaW5kZXggb2YgdGhlIHN3YXAgcGVyZm9ybWVkLiBTd2FwcyBhcmUgbnVtYmVyZWQgaW5jcmVhc2luZ2x5IGFzIHRoZXkgYXBwZWFyIGluIHRoZSBpbnB1dCwgc3RhcnRpbmcgZnJvbSAxLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #2 5번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: doju