시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 57 19 18 38.298%

문제

상근이는 친구들 중에 거짓말쟁이가 몇 명이나 있는지 알아내려고 한다. 상근이의 친구는 총 N명이며, 항상 거짓말만 하는 친구와 항상 진실만을 이야기하는 친구로 나누어 진다. (2 ≤ N ≤ 1000) 

상근이는 친구들에게 총 M번의 질문을 했다. (1 ≤ M ≤ 10,000) 질문은 x에게 "y가 거짓말쟁이이니?"와 같은 형식이다. x가 y는 거짓말쟁이라고 말했다면 상근이는 종이에 "x y L"라고 적을 것이고, 아니라면 "x y T"라고 적을 것이다.

이러한 질문은 여러 친구에게 물어봤으며, 같은 친구에게 같은 질문을 물어봤을 수도 있다. 하지만, 자기 자신이 거짓말쟁이라고 물어보는 질문은 하지 않는다.

안타깝게도, 상근이는 종이에 질문의 일부를 잘못 쓴 것 같다는 생각이 들었다. 따라서, 종이에 적힌 질문과 대답만으로 누가 거짓말쟁이이고 아닌지를 알아내지 못 할 수도 있다.

상근이가 적어놓은 질문과 대답을 주어진 순서대로 고려했을 때, 모순이 발생하지 않는 최대 개수를 출력하시오.

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 M개 줄에는 상근이의 질문에 대한 대답 정보이며, "x y L" 또는 "x y T" 형태이다.

출력

첫째 줄에 모순이 발생하지 않는 최대 개수를 출력한다.

예제 입력 1

4 3
1 4 L
2 3 T
4 1 T

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjU4NTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzBcdWM5ZDNcdWI5ZDBcdWM3YzFcdWM3NzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNlNWNcdWFkNmNcdWI0ZTQgXHVjOTExXHVjNWQwIFx1YWM3MFx1YzlkM1x1YjlkMFx1YzdjMVx1Yzc3NFx1YWMwMCBcdWJhODcgXHViYTg1XHVjNzc0XHViMDk4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjZTVjXHVhZDZjXHViMjk0IFx1Y2QxZCBOXHViYTg1XHVjNzc0XHViYTcwLCBcdWQ1NmRcdWMwYzEgXHVhYzcwXHVjOWQzXHViOWQwXHViOWNjIFx1ZDU1OFx1YjI5NCBcdWNlNWNcdWFkNmNcdWM2NDAgXHVkNTZkXHVjMGMxIFx1YzljNFx1YzJlNFx1YjljY1x1Yzc0NCBcdWM3NzRcdWM1N2NcdWFlMzBcdWQ1NThcdWIyOTQgXHVjZTVjXHVhZDZjXHViODVjIFx1YjA5OFx1YjIwNFx1YzViNCBcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDEwMDApJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNlNWNcdWFkNmNcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVjZDFkIE1cdWJjODhcdWM3NTggXHVjOWM4XHViYjM4XHVjNzQ0IFx1ZDU4OFx1YjJlNC4gKDEgJmxlOyBNICZsZTsgMTAsMDAwKSBcdWM5YzhcdWJiMzhcdWM3NDAgeFx1YzVkMFx1YWM4YyAmcXVvdDt5XHVhYzAwIFx1YWM3MFx1YzlkM1x1YjlkMFx1YzdjMVx1Yzc3NFx1Yzc3NFx1YjJjOD8mcXVvdDtcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1Yzc3NFx1YjJlNC4geFx1YWMwMCB5XHViMjk0IFx1YWM3MFx1YzlkM1x1YjlkMFx1YzdjMVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWI5ZDBcdWQ1ODhcdWIyZTRcdWJhNzQgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzg4NVx1Yzc3NFx1YzVkMCAmcXVvdDt4IHkgTCZxdW90O1x1Yjc3Y1x1YWNlMCBcdWM4MDFcdWM3NDQgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWM1NDRcdWIyYzhcdWI3N2NcdWJhNzQgJnF1b3Q7eCB5IFQmcXVvdDtcdWI3N2NcdWFjZTAgXHVjODAxXHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1YzljOFx1YmIzOFx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVjZTVjXHVhZDZjXHVjNWQwXHVhYzhjIFx1YmIzY1x1YzViNFx1YmQyNFx1YzczY1x1YmE3MCwgXHVhYzE5XHVjNzQwIFx1Y2U1Y1x1YWQ2Y1x1YzVkMFx1YWM4YyBcdWFjMTlcdWM3NDAgXHVjOWM4XHViYjM4XHVjNzQ0IFx1YmIzY1x1YzViNFx1YmQyNFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVhYzcwXHVjOWQzXHViOWQwXHVjN2MxXHVjNzc0XHViNzdjXHVhY2UwIFx1YmIzY1x1YzViNFx1YmNmNFx1YjI5NCBcdWM5YzhcdWJiMzhcdWM3NDAgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ4XHVkMGMwXHVhZTVkXHVhYzhjXHViM2M0LCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjODg1XHVjNzc0XHVjNWQwIFx1YzljOFx1YmIzOFx1Yzc1OCBcdWM3N2NcdWJkODBcdWI5N2MgXHVjNzk4XHViYWJiIFx1YzRmNCBcdWFjODMgXHVhYzE5XHViMmU0XHViMjk0IFx1YzBkZFx1YWMwMVx1Yzc3NCBcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjODg1XHVjNzc0XHVjNWQwIFx1YzgwMVx1ZDc4YyBcdWM5YzhcdWJiMzhcdWFjZmMgXHViMzAwXHViMmY1XHViOWNjXHVjNzNjXHViODVjIFx1YjIwNFx1YWMwMCBcdWFjNzBcdWM5ZDNcdWI5ZDBcdWM3YzFcdWM3NzRcdWM3NzRcdWFjZTAgXHVjNTQ0XHViMmNjXHVjOWMwXHViOTdjIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YzljMCBcdWJhYmIgXHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM4MDFcdWM1YjRcdWIxOTNcdWM3NDAgXHVjOWM4XHViYjM4XHVhY2ZjIFx1YjMwMFx1YjJmNVx1Yzc0NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YWNlMFx1YjgyNFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YzIxY1x1Yzc3NCBcdWJjMWNcdWMwZGRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YjMwMFx1YjJmNSBcdWM4MTVcdWJjZjRcdWM3NzRcdWJhNzAsICZxdW90O3ggeSBMJnF1b3Q7IFx1YjYxMFx1YjI5NCAmcXVvdDt4IHkgVCZxdW90OyBcdWQ2MTVcdWQwZGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJhYThcdWMyMWNcdWM3NzQgXHViYzFjXHVjMGRkXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1ODU5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGlhcnMgYW5kIFRydXRoIFRlbGxlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkFmdGVyIHNwZW5kaW5nIHNvIG11Y2ggdGltZSBhcm91bmQgaGlzIGNvd3MsIEZhcm1lciBKb2huIGhhcyBzdGFydGVkIHRvIHVuZGVyc3RhbmQgdGhlaXIgbGFuZ3VhZ2UuICZuYnNwO01vcmVvdmVyLCBoZSBub3RpY2VzIHRoYXQgYW1vbmcgaGlzIE4gY293cyAoMiAmbHQ7PSBOICZsdDs9IDEwMDApLCBzb21lIGFsd2F5cyB0ZWxsIHRoZSB0cnV0aCB3aGlsZSBvdGhlcnMgYWx3YXlzIGxpZS48XC9wPlxyXG5cclxuPHA+RkogY2FyZWZ1bGx5IGxpc3RlbnMgdG8gTSBzdGF0ZW1lbnRzICgxICZsdDs9IE0gJmx0Oz0gMTAsMDAwKSBmcm9tIGhpcyBjb3dzLCBlYWNoIG9mIHRoZSBmb3JtICZxdW90O3ggeSBUJnF1b3Q7LCBtZWFuaW5nIHRoYXQgJnF1b3Q7Y293IHggY2xhaW1zIGNvdyB5IGFsd2F5cyB0ZWxscyB0aGUgdHJ1dGgmcXVvdDsgb3IgJnF1b3Q7eCB5IEwmcXVvdDssIG1lYW5pbmcgdGhhdCAmcXVvdDtjb3cgeCBjbGFpbXMgY293IHkgYWx3YXlzIHRlbGxzIGxpZXMmcXVvdDsuIEVhY2ggc3RhdGVtZW50IGludm9sdmVzIGEgcGFpciBvZiBkaWZmZXJlbnQgY293cywgYW5kIHRoZSBzYW1lIHBhaXIgb2YgY293cyBtYXkgYXBwZWFyIGluIG11bHRpcGxlIHN0YXRlbWVudHMuICZuYnNwOzxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCBGSiBiZWxpZXZlcyBoZSBtaWdodCBoYXZlIHdyaXR0ZW4gZG93biBzb21lIGVudHJpZXMgaW4gaGlzIGxpc3QgaW5jb3JyZWN0bHksIHNvIHRoZXJlIG1heSBub3QgYmUgYSB2YWxpZCB3YXkgdG8gZGVzaWduYXRlIGVhY2ggY293IGFzIGEgdHJ1dGggdGVsbGVyIG9yIGEgbGlhciB0aGF0IGlzIGNvbnNpc3RlbnQgd2l0aCBhbGwgdGhlIE0gc3RhdGVtZW50cyBvbiBGSiYjMzk7cyBsaXN0LiAmbmJzcDtUbyBoZWxwIEZKIHNhbHZhZ2UgYXMgbXVjaCBvZiBoaXMgbGlzdCBhcyBwb3NzaWJsZSwgcGxlYXNlIGNvbXB1dGUgdGhlIGxhcmdlc3QgdmFsdWUgb2YgQSBzdWNoIHRoYXQgdGhlcmUgZXhpc3RzIGEgdmFsaWQgd2F5IHRvIGRlc2lnbmF0ZSBlYWNoIGNvdyBhcyBhIHRydXRoIHRlbGxlciBvciBhIGxpYXIgaW4gYSBtYW5uZXIgdGhhdCBpcyBjb25zaXN0ZW50IHdpdGggdGhlIGZpcnN0IEEgZW50cmllcyBpbiBGSiYjMzk7cyBsaXN0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIE4gYW5kIE0uPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uMStNOiBFYWNoIGxpbmUgaXMgb2YgdGhlIGZvcm0gJnF1b3Q7eCB5IEwmcXVvdDsgb3IgJnF1b3Q7eCB5IFQmcXVvdDssIGRlc2NyaWJpbmcgYSBzdGF0ZW1lbnQgbWFkZSBieSBjb3cgeCBhYm91dCBjb3cgeS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogVGhlIG1heGltdW0gdmFsdWUgb2YgQSBzdWNoIHRoYXQgdGhlIGZpcnN0IEEgZW50cmllcyBpbiBGSiYjMzk7cyBsaXN0IGNhbiBiZSBjb25zaXN0ZW50IHdpdGggc29tZSBhc3NpZ25tZW50IG9mICZxdW90O3RydXRoIHRlbGxlciZxdW90OyBvciAmcXVvdDtsaWFyJnF1b3Q7IHRvIHRoZSBOIGNvd3MuPFwvcD5cclxuIiwiaGludCI6IjxwPlN0YXRlbWVudHMgMSBhbmQgMyBjYW5ub3QgYm90aCBiZSBzYXRpc2ZpZWQgYXQgdGhlIHNhbWUgdGltZSwgYnV0IHN0YXRlbWVudHMgMSBhbmQgMiBjYW4gYmUsIGlmIHdlIGxldCBjb3dzIDEuLjMgdGVsbCB0aGUgdHJ1dGggYW5kIGNvdyA0IGJlIGEgbGlhci48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=