시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 603 210 163 36.303%

문제

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

  1. 내 친구의 친구는 내 친구이다.
  2. 내 원수의 원수도 내 친구이다.

이 때 두 학생이 친구이면 같은 팀에 속해있어야 하며, 같은 팀에 속해 있는 사람들끼리는 전부 친구여야 한다.

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

입력

첫째 줄에 학생의 수 n이 주어진다. 각 학생들은 1부터 n까지 번호가 매겨져 있다. (2 ≤ n ≤ 1000) 

둘째 줄에 학생 간의 인간관계 중 알려진 것의 개수 m이 주어진다. (1 ≤ m ≤ 5000)

다음 m개의 줄에는 한 줄에 한 개씩, 학생 간의 인간관계가 F p q 혹은 E p q의 형태로 공백으로 구분되어 주어진다. (1 ≤ p < q ≤ N)

첫 번째 글자가 F인 경우에는 p와 q가 친구인 것이고, E인 경우는 p와 q가 원수인 경우이다. 

입력은 모순이 없음이 보장된다. 즉, 두 학생이 동시에 친구이면서 원수인 경우는 없다.

출력

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

예제 입력 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+XHJcblx0PGxpPlx1YjBiNCBcdWNlNWNcdWFkNmNcdWM3NTggXHVjZTVjXHVhZDZjXHViMjk0IFx1YjBiNCBcdWNlNWNcdWFkNmNcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjBiNCBcdWM2ZDBcdWMyMThcdWM3NTggXHVjNmQwXHVjMjE4XHViM2M0Jm5ic3A7XHViMGI0IFx1Y2U1Y1x1YWQ2Y1x1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM3NzQgXHViNTRjIFx1YjQ1MCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjZTVjXHVhZDZjXHVjNzc0XHViYTc0IFx1YWMxOVx1Yzc0MCBcdWQzMDBcdWM1ZDAgXHVjMThkXHVkNTc0XHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVhYzE5XHVjNzQwIFx1ZDMwMFx1YzVkMCBcdWMxOGRcdWQ1NzQgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1YjA3Y1x1YjlhY1x1YjI5NCBcdWM4MDRcdWJkODAgXHVjZTVjXHVhZDZjXHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1Yzc3OFx1YWMwNFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQsIFx1YjJlZFx1YzJmOFx1YzZjMFx1Yzc0NCBcdWM3MDRcdWQ1NWMgXHVkMzAwIFx1YzgxNVx1ZDU1OFx1YWUzMFx1Yjk3YyBcdWQ1NjAgXHViNTRjLCBcdWNkNWNcdWIzMDAgXHVjNWJjXHViOWM4XHViMDk4IFx1YjljZVx1Yzc0MCBcdWQzMDBcdWM3NzQgXHViOWNjXHViNGU0XHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LiAoMiAmbGU7IG4gJmxlOyAxMDAwKSZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU1OVx1YzBkZCBcdWFjMDRcdWM3NTggXHVjNzc4XHVhYzA0XHVhZDAwXHVhY2M0IFx1YzkxMSBcdWM1NGNcdWI4MjRcdWM5YzQgXHVhYzgzXHVjNzU4IFx1YWMxY1x1YzIxOCBtXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBtICZsZTsgNTAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTVjIFx1YWMxY1x1YzUyOSwgXHVkNTU5XHVjMGRkIFx1YWMwNFx1Yzc1OCBcdWM3NzhcdWFjMDRcdWFkMDBcdWFjYzRcdWFjMDAgRiBwIHEgXHVkNjM5XHVjNzQwIEUgcCBxXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBwICZsdDsgcSAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHVhYzAwIEZcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IHBcdWM2NDAgcVx1YWMwMCBcdWNlNWNcdWFkNmNcdWM3NzggXHVhYzgzXHVjNzc0XHVhY2UwLCBFXHVjNzc4IFx1YWNiZFx1YzZiMFx1YjI5NCBwXHVjNjQwIHFcdWFjMDAgXHVjNmQwXHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YmFhOFx1YzIxY1x1Yzc3NCBcdWM1YzZcdWM3NGNcdWM3NzQgXHViY2Y0XHVjN2E1XHViNDFjXHViMmU0LiBcdWM5ODksIFx1YjQ1MCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1Y2U1Y1x1YWQ2Y1x1Yzc3NFx1YmE3NFx1YzExYyBcdWM2ZDBcdWMyMThcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwLCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHViMzAwIFx1ZDMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD4xXHViYzg4IFx1ZDU1OVx1YzBkZCBcdWQ2M2NcdWM3OTAgXHVkMzAwLCAyLCA0LCA2XHViYzg4IFx1ZDU1OVx1YzBkZCBcdWMxNGJcdWM3NzRcdWMxMWMgXHVkMzAwLCAzLCA1XHViYzg4IFx1ZDU1OVx1YzBkZCBcdWI0NThcdWM3NzRcdWMxMWMgXHVkMzAwXHVjNzdjIFx1YjU0YywgXHVkMzAwXHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWNkNWNcdWIzMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzY1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEdhbmdzIiwiZGVzY3JpcHRpb24iOiI8cD5DaGljYWdvIGluIHRoZSAxOTIwczogYSBiYXR0bGVmaWVsZCBvZiBnYW5nc3RlcnMuPFwvcD5cclxuXHJcbjxwPklmIHR3byBnYW5nc3RlcnMgaGF2ZSBldmVyIG1ldCBlYWNoIG90aGVyLCB0aGVuIHRoZXkgaGF2ZSBiZWNvbWUgZWl0aGVyIHRydWUgZnJpZW5kcyBvciBtb3J0YWwgZW5lbWllcy4gVGhlIGdhbmdzdGVycyBsaXZlIC0gYW5kIGRpZSAtIGJ5IHRoZSBmb2xsb3dpbmcgY29kZSBvZiBldGhpY3MuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+QSBmcmllbmQgb2YgbXkgZnJpZW5kIGlzIGFsc28gbXkgZnJpZW5kLjxcL2xpPlxyXG5cdDxsaT5BbiBlbmVteSBvZiBteSBlbmVteSBpcyBteSBmcmllbmQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+VHdvIGdhbmdzdGVycyBhcmUgaW4gdGhlIHNhbWUgZ2FuZyBpZiBhbmQgb25seSBpZiB0aGV5IGFyZSBmcmllbmRzLjxcL3A+XHJcblxyXG48cD5Qb29yIHlvdSBhcmUgZW1wbG95ZWQgYnkgdGhlIENoaWNhZ28gUG9saWNlIERlcGFydG1lbnQuIFlvdSBtdXN0IGNhbGN1bGF0ZSB0aGUgbWF4aW1hbCBwb3NzaWJsZSBudW1iZXIgb2YgZGlmZmVyZW50IGdhbmdzIGluIENoaWNhZ28gYmFzZWQgb24gd2hhdCB0aGUgRGVwYXJ0bWVudCBrbm93cyBhYm91dCB0aGUgcmVsYXRpb25zIGJldHdlZW4gdGhlIGluZGl2aWR1YWwgZ2FuZ3N0ZXJzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGdpdmVzIHRoZSBudW1iZXIgTiAoMiAmbGU7IE4gJmxlOyAxIDAwMCkgb2Yga25vd24gZ2FuZ3N0ZXJzLiBUaGUgZ2FuZ3N0ZXJzIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gTi4gVGhlIHNlY29uZCBsaW5lIGdpdmVzIHRoZSBudW1iZXIgTSAoMSAmbGU7IE0gJmxlOyA1IDAwMCkgb2Yga25vd24gZmFjdHMgYWJvdXQgdGhlc2UgZ2FuZ3N0ZXJzLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE0gbGluZXMgbGlzdCB0aGUgZmFjdHMsIGVhY2ggZmFjdCBvbiBpdHMgb3duIGxpbmUuIEVhY2ggZmFjdCBpcyBvZiB0aGUgZm9ybSBGIHAgcSBvciBFIHAgcSwgd2hlcmUgMSAmbGU7IHAgJmx0OyBxICZsZTsgTiBhcmUgdGhlIHR3byBnYW5nc3RlcnMgaW4gcXVlc3Rpb24uIChFYWNoIG9mIHRocmVlIGNvbXBvbmVudHMgaXMgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuKSBJZiB0aGUgZmlyc3QgbGV0dGVyIGlzIEYsIHRoZSBsaW5lIHNheXMgdGhhdCBwIGFuZCBxIGFyZSBrbm93biBmcmllbmRzLiBJZiBpdCBpcyBFLCB0aGVuIHRoZXkgYXJlIGtub3duIGVuZW1pZXMuPFwvcD5cclxuXHJcbjxwPkl0IGNhbiBiZSBhc3N1bWUgdGhhdCB0aGUgaW5wdXQgaXMgY29uc2lzdGVudCAtIHR3byBnYW5nc3RlcnMgY2Fubm90IGJlIGJvdGggZnJpZW5kcyBhbmQgZW5lbWllcyBvZiBlYWNoIG90aGVyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIHRoZSBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBtYXhpbWFsIHBvc3NpYmxlIG51bWJlciBvZiBnYW5ncy48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIDMgZ2FuZ3MgaW4gdGhlIGV4YW1wbGUgYWJvdmUgYXJlIHsxfSwgezIsNCw2fSwgYW5kIHszLDV9LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2003 4번

  • 문제를 번역한 사람: author5
  • 어색한 표현을 찾은 사람: Green55
  • 문제의 오타를 찾은 사람: jugol