시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 291 88 66 28.947%

문제

닭싸움은 월드의 전통이다. 이번 캠프에서도 어김없이 닭싸움 대회가 열렸다. 그런데, 닭싸움을 하기 위해서는 반드시 누가 우리 편이고, 누가 우리 편이 아닌지를 알아야 할 것이다. 닭싸움의 팀을 정하는 원칙은, 평소 학생들의 인간관계에 따라 다음과 같이 정리할 수 있다.

  1. 내 친구는 우리 편이다.
  2. 내 친구의 친구는 우리 편이다.
  3. 내 원수는 우리 편이 아니다.
  4. 내 원수의 원수는 우리 편이다.

학생들의 인간관계가 주어지면, 닭싸움을 위한 팀 정하기를 할 때, 최대 얼마나 많은 팀이 만들어질 수 있는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 학생의 수 n이 주어지고, 둘째 줄에 학생 간의 인간관계 중 알려진 것의 개수 m이 주어진다. (2<=n<=1000, 1<=m<=5000) 셋째 줄부터는 한 줄에 한 개씩 학생 간의 인간관계가 주어진다. 맨 먼저 이 관계가 친구 관계인지, 원수 관계인지를 나타내는 알파벳 대문자가 주어진다. F인 경우에는 친구인 것이고, E인 경우는 원수인 경우이다. 그 다음 두 학생의 번호가 주어진다.

출력

첫째 줄에, 가능한 최대 팀 개수를 출력한다.

예제 입력 1

6
4
E 1 4
F 3 5
F 4 6
E 1 2

예제 출력 1

3

힌트

1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다.

W3sicHJvYmxlbV9pZCI6IjE3NjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZWRcdWMyZjhcdWM2YzAgXHVkMzAwIFx1YzgxNVx1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHViMmVkXHVjMmY4XHVjNmMwXHVjNzQwIFx1YzZkNFx1YjRkY1x1Yzc1OCBcdWM4MDRcdWQxYjVcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YmM4OCBcdWNlYTBcdWQ1MDRcdWM1ZDBcdWMxMWNcdWIzYzQgXHVjNWI0XHVhZTQwXHVjNWM2XHVjNzc0IFx1YjJlZFx1YzJmOFx1YzZjMCBcdWIzMDBcdWQ2OGNcdWFjMDAgXHVjNWY0XHViODM4XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAsIFx1YjJlZFx1YzJmOFx1YzZjMFx1Yzc0NCBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YmMxOFx1YjRkY1x1YzJkYyBcdWIyMDRcdWFjMDAgXHVjNmIwXHViOWFjIFx1ZDNiOFx1Yzc3NFx1YWNlMCwgXHViMjA0XHVhYzAwIFx1YzZiMFx1YjlhYyBcdWQzYjhcdWM3NzQgXHVjNTQ0XHViMmNjXHVjOWMwXHViOTdjIFx1YzU0Y1x1YzU0NFx1YzU3YyBcdWQ1NjAgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWIyZWRcdWMyZjhcdWM2YzBcdWM3NTggXHVkMzAwXHVjNzQ0IFx1YzgxNVx1ZDU1OFx1YjI5NCBcdWM2ZDBcdWNlNTlcdWM3NDAsIFx1ZDNjOVx1YzE4YyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjNzc4XHVhYzA0XHVhZDAwXHVhY2M0XHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YjBiNCBcdWNlNWNcdWFkNmNcdWIyOTQgXHVjNmIwXHViOWFjIFx1ZDNiOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMGI0IFx1Y2U1Y1x1YWQ2Y1x1Yzc1OCBcdWNlNWNcdWFkNmNcdWIyOTQgXHVjNmIwXHViOWFjIFx1ZDNiOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMGI0IFx1YzZkMFx1YzIxOFx1YjI5NCBcdWM2YjBcdWI5YWMgXHVkM2I4XHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMGI0IFx1YzZkMFx1YzIxOFx1Yzc1OCBcdWM2ZDBcdWMyMThcdWIyOTQgXHVjNmIwXHViOWFjIFx1ZDNiOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NTggXHVjNzc4XHVhYzA0XHVhZDAwXHVhY2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCwgXHViMmVkXHVjMmY4XHVjNmMwXHVjNzQ0IFx1YzcwNFx1ZDU1YyBcdWQzMDAgXHVjODE1XHVkNTU4XHVhZTMwXHViOTdjIFx1ZDU2MCBcdWI1NGMsIFx1Y2Q1Y1x1YjMwMCBcdWM1YmNcdWI5YzhcdWIwOTggXHViOWNlXHVjNzQwIFx1ZDMwMFx1Yzc3NCBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NTlcdWMwZGQgXHVhYzA0XHVjNzU4IFx1Yzc3OFx1YWMwNFx1YWQwMFx1YWNjNCBcdWM5MTEgXHVjNTRjXHViODI0XHVjOWM0IFx1YWM4M1x1Yzc1OCBcdWFjMWNcdWMyMTggbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyJmx0Oz1uJmx0Oz0xMDAwLCAxJmx0Oz1tJmx0Oz01MDAwKSBcdWMxNGJcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTVjIFx1YWMxY1x1YzUyOSBcdWQ1NTlcdWMwZGQgXHVhYzA0XHVjNzU4IFx1Yzc3OFx1YWMwNFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjllOCBcdWJhM2NcdWM4MDAgXHVjNzc0IFx1YWQwMFx1YWNjNFx1YWMwMCBcdWNlNWNcdWFkNmMgXHVhZDAwXHVhY2M0XHVjNzc4XHVjOWMwLCBcdWM2ZDBcdWMyMTggXHVhZDAwXHVhY2M0XHVjNzc4XHVjOWMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gRlx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjZTVjXHVhZDZjXHVjNzc4IFx1YWM4M1x1Yzc3NFx1YWNlMCwgRVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNmQwXHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWI0NTAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCwgXHVhYzAwXHViMmE1XHVkNTVjIFx1Y2Q1Y1x1YjMwMCBcdWQzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+MVx1YmM4OCBcdWQ1NTlcdWMwZGQgXHVkNjNjXHVjNzkwIFx1ZDMwMCwgMiwgNCwgNlx1YmM4OCBcdWQ1NTlcdWMwZGQgXHVjMTRiXHVjNzc0XHVjMTFjIFx1ZDMwMCwgMywgNVx1YmM4OCBcdWQ1NTlcdWMwZGQgXHViNDU4XHVjNzc0XHVjMTFjIFx1ZDMwMFx1Yzc3YyBcdWI1NGMsIFx1ZDMwMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjZDVjXHViMzAwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTc2NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBHYW5ncyIsImRlc2NyaXB0aW9uIjoiPHA+Q2hpY2FnbyBpbiB0aGUgMTkyMHM6IGEgYmF0dGxlZmllbGQgb2YgZ2FuZ3N0ZXJzLjxcL3A+XHJcblxyXG48cD5JZiB0d28gZ2FuZ3N0ZXJzIGhhdmUgZXZlciBtZXQgZWFjaCBvdGhlciwgdGhlbiB0aGV5IGhhdmUgYmVjb21lIGVpdGhlciB0cnVlIGZyaWVuZHMgb3IgbW9ydGFsIGVuZW1pZXMuIFRoZSBnYW5nc3RlcnMgbGl2ZSAtIGFuZCBkaWUgLSBieSB0aGUgZm9sbG93aW5nIGNvZGUgb2YgZXRoaWNzLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkEgZnJpZW5kIG9mIG15IGZyaWVuZCBpcyBhbHNvIG15IGZyaWVuZC48XC9saT5cclxuXHQ8bGk+QW4gZW5lbXkgb2YgbXkgZW5lbXkgaXMgbXkgZnJpZW5kLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlR3byBnYW5nc3RlcnMgYXJlIGluIHRoZSBzYW1lIGdhbmcgaWYgYW5kIG9ubHkgaWYgdGhleSBhcmUgZnJpZW5kcy48XC9wPlxyXG5cclxuPHA+UG9vciB5b3UgYXJlIGVtcGxveWVkIGJ5IHRoZSBDaGljYWdvIFBvbGljZSBEZXBhcnRtZW50LiBZb3UgbXVzdCBjYWxjdWxhdGUgdGhlIG1heGltYWwgcG9zc2libGUgbnVtYmVyIG9mIGRpZmZlcmVudCBnYW5ncyBpbiBDaGljYWdvIGJhc2VkIG9uIHdoYXQgdGhlIERlcGFydG1lbnQga25vd3MgYWJvdXQgdGhlIHJlbGF0aW9ucyBiZXR3ZWVuIHRoZSBpbmRpdmlkdWFsIGdhbmdzdGVycy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBnaXZlcyB0aGUgbnVtYmVyIE4gKDIgJmxlOyBOICZsZTsgMSAwMDApIG9mIGtub3duIGdhbmdzdGVycy4gVGhlIGdhbmdzdGVycyBhcmUgbnVtYmVyZWQgZnJvbSAxIHRvIE4uIFRoZSBzZWNvbmQgbGluZSBnaXZlcyB0aGUgbnVtYmVyIE0gKDEgJmxlOyBNICZsZTsgNSAwMDApIG9mIGtub3duIGZhY3RzIGFib3V0IHRoZXNlIGdhbmdzdGVycy48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBNIGxpbmVzIGxpc3QgdGhlIGZhY3RzLCBlYWNoIGZhY3Qgb24gaXRzIG93biBsaW5lLiBFYWNoIGZhY3QgaXMgb2YgdGhlIGZvcm0gRiBwIHEgb3IgRSBwIHEsIHdoZXJlIDEgJmxlOyBwICZsdDsgcSAmbGU7IE4gYXJlIHRoZSB0d28gZ2FuZ3N0ZXJzIGluIHF1ZXN0aW9uLiAoRWFjaCBvZiB0aHJlZSBjb21wb25lbnRzIGlzIHNlcGFyYXRlZCBieSBhIHNwYWNlLikgSWYgdGhlIGZpcnN0IGxldHRlciBpcyBGLCB0aGUgbGluZSBzYXlzIHRoYXQgcCBhbmQgcSBhcmUga25vd24gZnJpZW5kcy4gSWYgaXQgaXMgRSwgdGhlbiB0aGV5IGFyZSBrbm93biBlbmVtaWVzLjxcL3A+XHJcblxyXG48cD5JdCBjYW4gYmUgYXNzdW1lIHRoYXQgdGhlIGlucHV0IGlzIGNvbnNpc3RlbnQgLSB0d28gZ2FuZ3N0ZXJzIGNhbm5vdCBiZSBib3RoIGZyaWVuZHMgYW5kIGVuZW1pZXMgb2YgZWFjaCBvdGhlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiB0aGUgb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbWF4aW1hbCBwb3NzaWJsZSBudW1iZXIgb2YgZ2FuZ3MuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSAzIGdhbmdzIGluIHRoZSBleGFtcGxlIGFib3ZlIGFyZSB7MX0sIHsyLDQsNn0sIGFuZCB7Myw1fS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2003 4번

  • 문제를 번역한 사람: author5
  • 문제의 오타를 찾은 사람: jugol