시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 496 151 115 31.421%

문제

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

  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+XHViMmU0XHVjNzRjIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTVjIFx1YWMxY1x1YzUyOSwgXHVkNTU5XHVjMGRkIFx1YWMwNFx1Yzc1OCBcdWM3NzhcdWFjMDRcdWFkMDBcdWFjYzRcdWFjMDAgRiBwIHEgXHVkNjM5XHVjNzQwIEUgcCBxXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBwICZsdDsgcSAmbGU7IE4pPFwvcD5cclxuXHJcbjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWFlMDBcdWM3OTBcdWFjMDAgRlx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgcFx1YzY0MCBxXHVhYzAwIFx1Y2U1Y1x1YWQ2Y1x1Yzc3OCBcdWFjODNcdWM3NzRcdWFjZTAsIEVcdWM3NzggXHVhY2JkXHVjNmIwXHViMjk0IHBcdWM2NDAgcVx1YWMwMCBcdWM2ZDBcdWMyMThcdWM3NzggXHVhY2JkXHVjNmIwXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHViYWE4XHVjMjFjXHVjNzc0IFx1YzVjNlx1Yzc0Y1x1Yzc3NCBcdWJjZjRcdWM3YTVcdWI0MWNcdWIyZTQuIFx1Yzk4OSwgXHViNDUwIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVjZTVjXHVhZDZjXHVjNzc0XHViYTc0XHVjMTFjIFx1YzZkMFx1YzIxOFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWNkNWNcdWIzMDAgXHVkMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjFcdWJjODggXHVkNTU5XHVjMGRkIFx1ZDYzY1x1Yzc5MCBcdWQzMDAsIDIsIDQsIDZcdWJjODggXHVkNTU5XHVjMGRkIFx1YzE0Ylx1Yzc3NFx1YzExYyBcdWQzMDAsIDMsIDVcdWJjODggXHVkNTU5XHVjMGRkIFx1YjQ1OFx1Yzc3NFx1YzExYyBcdWQzMDBcdWM3N2MgXHViNTRjLCBcdWQzMDBcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE3NjUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgR2FuZ3MiLCJkZXNjcmlwdGlvbiI6IjxwPkNoaWNhZ28gaW4gdGhlIDE5MjBzOiBhIGJhdHRsZWZpZWxkIG9mIGdhbmdzdGVycy48XC9wPlxyXG5cclxuPHA+SWYgdHdvIGdhbmdzdGVycyBoYXZlIGV2ZXIgbWV0IGVhY2ggb3RoZXIsIHRoZW4gdGhleSBoYXZlIGJlY29tZSBlaXRoZXIgdHJ1ZSBmcmllbmRzIG9yIG1vcnRhbCBlbmVtaWVzLiBUaGUgZ2FuZ3N0ZXJzIGxpdmUgLSBhbmQgZGllIC0gYnkgdGhlIGZvbGxvd2luZyBjb2RlIG9mIGV0aGljcy48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5BIGZyaWVuZCBvZiBteSBmcmllbmQgaXMgYWxzbyBteSBmcmllbmQuPFwvbGk+XHJcblx0PGxpPkFuIGVuZW15IG9mIG15IGVuZW15IGlzIG15IGZyaWVuZC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Ud28gZ2FuZ3N0ZXJzIGFyZSBpbiB0aGUgc2FtZSBnYW5nIGlmIGFuZCBvbmx5IGlmIHRoZXkgYXJlIGZyaWVuZHMuPFwvcD5cclxuXHJcbjxwPlBvb3IgeW91IGFyZSBlbXBsb3llZCBieSB0aGUgQ2hpY2FnbyBQb2xpY2UgRGVwYXJ0bWVudC4gWW91IG11c3QgY2FsY3VsYXRlIHRoZSBtYXhpbWFsIHBvc3NpYmxlIG51bWJlciBvZiBkaWZmZXJlbnQgZ2FuZ3MgaW4gQ2hpY2FnbyBiYXNlZCBvbiB3aGF0IHRoZSBEZXBhcnRtZW50IGtub3dzIGFib3V0IHRoZSByZWxhdGlvbnMgYmV0d2VlbiB0aGUgaW5kaXZpZHVhbCBnYW5nc3RlcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZ2l2ZXMgdGhlIG51bWJlciBOICgyICZsZTsgTiAmbGU7IDEgMDAwKSBvZiBrbm93biBnYW5nc3RlcnMuIFRoZSBnYW5nc3RlcnMgYXJlIG51bWJlcmVkIGZyb20gMSB0byBOLiBUaGUgc2Vjb25kIGxpbmUgZ2l2ZXMgdGhlIG51bWJlciBNICgxICZsZTsgTSAmbGU7IDUgMDAwKSBvZiBrbm93biBmYWN0cyBhYm91dCB0aGVzZSBnYW5nc3RlcnMuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgTSBsaW5lcyBsaXN0IHRoZSBmYWN0cywgZWFjaCBmYWN0IG9uIGl0cyBvd24gbGluZS4gRWFjaCBmYWN0IGlzIG9mIHRoZSBmb3JtIEYgcCBxIG9yIEUgcCBxLCB3aGVyZSAxICZsZTsgcCAmbHQ7IHEgJmxlOyBOIGFyZSB0aGUgdHdvIGdhbmdzdGVycyBpbiBxdWVzdGlvbi4gKEVhY2ggb2YgdGhyZWUgY29tcG9uZW50cyBpcyBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4pIElmIHRoZSBmaXJzdCBsZXR0ZXIgaXMgRiwgdGhlIGxpbmUgc2F5cyB0aGF0IHAgYW5kIHEgYXJlIGtub3duIGZyaWVuZHMuIElmIGl0IGlzIEUsIHRoZW4gdGhleSBhcmUga25vd24gZW5lbWllcy48XC9wPlxyXG5cclxuPHA+SXQgY2FuIGJlIGFzc3VtZSB0aGF0IHRoZSBpbnB1dCBpcyBjb25zaXN0ZW50IC0gdHdvIGdhbmdzdGVycyBjYW5ub3QgYmUgYm90aCBmcmllbmRzIGFuZCBlbmVtaWVzIG9mIGVhY2ggb3RoZXIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1heGltYWwgcG9zc2libGUgbnVtYmVyIG9mIGdhbmdzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgMyBnYW5ncyBpbiB0aGUgZXhhbXBsZSBhYm92ZSBhcmUgezF9LCB7Miw0LDZ9LCBhbmQgezMsNX0uPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2003 4번

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