시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 43 16 15 45.455%

문제

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

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

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

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

상근이가 적어 놓은 질문과 대답 중 처음 A개만 가지고 누가 거짓말쟁이이고 아닌지 알아낼 수 있는 알아내는 프로그램을 작성하시오. 만약 알아낼 수 있다면, A의 최대값을 출력한다.

입력

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

출력

첫째 줄에 최대 A값을 출력한다.

예제 입력 1

4 3
1 4 L
2 3 T
4 1 T

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjU4NTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjNzBcdWM5ZDNcdWI5ZDBcdWM3YzFcdWM3NzQiLCJkZXNjcmlwdGlvbiI6IlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1YjRlNCBcdWM5MTFcdWM1ZDAgXHVhYzcwXHVjOWQzXHViOWQwXHVjN2MxXHVjNzc0XHVhYzAwIFx1YmE4NyBcdWJhODVcdWM3NzRcdWIwOTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yzc1OCBcdWNlNWNcdWFkNmNcdWIyOTQgXHVjZDFkIE5cdWJhODVcdWM3NzRcdWJhNzAsIFx1ZDU2ZFx1YzBjMSBcdWFjNzBcdWM5ZDNcdWI5ZDBcdWI5Y2MgXHVkNTU4XHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1YzY0MCBcdWQ1NmRcdWMwYzEgXHVjOWM0XHVjMmU0XHViOWNjXHVjNzQ0IFx1Yzc3NFx1YzU3Y1x1YWUzMFx1ZDU1OFx1YjI5NCBcdWNlNWNcdWFkNmNcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0IFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwMCkmbmJzcDs8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2U1Y1x1YWQ2Y1x1YjRlNFx1YzVkMFx1YWM4YyBcdWNkMWQgTVx1YmM4OFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3NDQgXHVkNTg4XHViMmU0LiAoMSAmbGU7IE0gJmxlOyAxMCwwMDApIFx1YzljOFx1YmIzOFx1Yzc0MCB4XHVjNWQwXHVhYzhjICZxdW90O3lcdWFjMDAgXHVhYzcwXHVjOWQzXHViOWQwXHVjN2MxXHVjNzc0XHVjNzc0XHViMmM4PyZxdW90O1x1YzY0MCBcdWFjMTlcdWM3NDAgXHVkNjE1XHVjMmRkXHVjNzc0XHViMmU0LiB4XHVhYzAwIHlcdWIyOTQgXHVhYzcwXHVjOWQzXHViOWQwXHVjN2MxXHVjNzc0XHViNzdjXHVhY2UwIFx1YjlkMFx1ZDU4OFx1YjJlNFx1YmE3NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjODg1XHVjNzc0XHVjNWQwICZxdW90O3ggeSBMJnF1b3Q7XHViNzdjXHVhY2UwIFx1YzgwMVx1Yzc0NCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YzU0NFx1YjJjOFx1Yjc3Y1x1YmE3NCAmcXVvdDt4IHkgVCZxdW90O1x1Yjc3Y1x1YWNlMCBcdWM4MDFcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjOWM4XHViYjM4XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWNlNWNcdWFkNmNcdWM1ZDBcdWFjOGMgXHViYjNjXHVjNWI0XHViZDI0XHVjNzNjXHViYTcwLCBcdWFjMTlcdWM3NDAgXHVjZTVjXHVhZDZjXHVjNWQwXHVhYzhjIFx1YWMxOVx1Yzc0MCBcdWM5YzhcdWJiMzhcdWM3NDQgXHViYjNjXHVjNWI0XHViZDI0XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWFjNzBcdWM5ZDNcdWI5ZDBcdWM3YzFcdWM3NzRcdWI3N2NcdWFjZTAgXHViYjNjXHVjNWI0XHViY2Y0XHViMjk0IFx1YzljOFx1YmIzOFx1Yzc0MCBcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjOWM4XHViYjM4XHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yjk3YyBcdWM3OThcdWJhYmIgXHVjNGY0IFx1YWM4MyBcdWFjMTlcdWIyZTRcdWIyOTQgXHVjMGRkXHVhYzAxXHVjNzc0IFx1YjRlNFx1YzVjOFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjODAxXHVkNzhjIFx1YzljOFx1YmIzOFx1YWNmYyBcdWIzMDBcdWIyZjVcdWI5Y2NcdWM3M2NcdWI4NWMgXHViMjA0XHVhYzAwIFx1YWM3MFx1YzlkM1x1YjlkMFx1YzdjMVx1Yzc3NFx1Yzc3NFx1YWNlMCBcdWM1NDRcdWIyY2NcdWM5YzBcdWI5N2MgXHVjNTRjXHVjNTQ0XHViMGI0XHVjOWMwIFx1YmFiYiBcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzgwMVx1YzViNCBcdWIxOTNcdWM3NDAgXHVjOWM4XHViYjM4XHVhY2ZjIFx1YjMwMFx1YjJmNSBcdWM5MTEgXHVjYzk4XHVjNzRjIEFcdWFjMWNcdWI5Y2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YjIwNFx1YWMwMCBcdWFjNzBcdWM5ZDNcdWI5ZDBcdWM3YzFcdWM3NzRcdWM3NzRcdWFjZTAgXHVjNTQ0XHViMmNjXHVjOWMwIFx1YzU0Y1x1YzU0NFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWI5Y2NcdWM1N2QgXHVjNTRjXHVjNTQ0XHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWJhNzQsIEFcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHVjOWM4XHViYjM4XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIzMDBcdWIyZjUgXHVjODE1XHViY2Y0XHVjNzc0XHViYTcwLCAmcXVvdDt4IHkgTCZxdW90OyBcdWI2MTBcdWIyOTQgJnF1b3Q7eCB5IFQmcXVvdDsgXHVkNjE1XHVkMGRjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMzAwIEFcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU4NTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMaWFycyBhbmQgVHJ1dGggVGVsbGVycyIsImRlc2NyaXB0aW9uIjoiPHA+QWZ0ZXIgc3BlbmRpbmcgc28gbXVjaCB0aW1lIGFyb3VuZCBoaXMgY293cywgRmFybWVyIEpvaG4gaGFzIHN0YXJ0ZWQgdG8gdW5kZXJzdGFuZCB0aGVpciBsYW5ndWFnZS4gJm5ic3A7TW9yZW92ZXIsIGhlIG5vdGljZXMgdGhhdCBhbW9uZyBoaXMgTiBjb3dzICgyICZsdDs9IE4gJmx0Oz0gMTAwMCksIHNvbWUgYWx3YXlzIHRlbGwgdGhlIHRydXRoIHdoaWxlIG90aGVycyBhbHdheXMgbGllLjxcL3A+XHJcblxyXG48cD5GSiBjYXJlZnVsbHkgbGlzdGVucyB0byBNIHN0YXRlbWVudHMgKDEgJmx0Oz0gTSAmbHQ7PSAxMCwwMDApIGZyb20gaGlzIGNvd3MsIGVhY2ggb2YgdGhlIGZvcm0gJnF1b3Q7eCB5IFQmcXVvdDssIG1lYW5pbmcgdGhhdCAmcXVvdDtjb3cgeCBjbGFpbXMgY293IHkgYWx3YXlzIHRlbGxzIHRoZSB0cnV0aCZxdW90OyBvciAmcXVvdDt4IHkgTCZxdW90OywgbWVhbmluZyB0aGF0ICZxdW90O2NvdyB4IGNsYWltcyBjb3cgeSBhbHdheXMgdGVsbHMgbGllcyZxdW90Oy4gRWFjaCBzdGF0ZW1lbnQgaW52b2x2ZXMgYSBwYWlyIG9mIGRpZmZlcmVudCBjb3dzLCBhbmQgdGhlIHNhbWUgcGFpciBvZiBjb3dzIG1heSBhcHBlYXIgaW4gbXVsdGlwbGUgc3RhdGVtZW50cy4gJm5ic3A7PFwvcD5cclxuXHJcbjxwPlVuZm9ydHVuYXRlbHksIEZKIGJlbGlldmVzIGhlIG1pZ2h0IGhhdmUgd3JpdHRlbiBkb3duIHNvbWUgZW50cmllcyBpbiBoaXMgbGlzdCBpbmNvcnJlY3RseSwgc28gdGhlcmUgbWF5IG5vdCBiZSBhIHZhbGlkIHdheSB0byBkZXNpZ25hdGUgZWFjaCBjb3cgYXMgYSB0cnV0aCB0ZWxsZXIgb3IgYSBsaWFyIHRoYXQgaXMgY29uc2lzdGVudCB3aXRoIGFsbCB0aGUgTSBzdGF0ZW1lbnRzIG9uIEZKJiMzOTtzIGxpc3QuICZuYnNwO1RvIGhlbHAgRkogc2FsdmFnZSBhcyBtdWNoIG9mIGhpcyBsaXN0IGFzIHBvc3NpYmxlLCBwbGVhc2UgY29tcHV0ZSB0aGUgbGFyZ2VzdCB2YWx1ZSBvZiBBIHN1Y2ggdGhhdCB0aGVyZSBleGlzdHMgYSB2YWxpZCB3YXkgdG8gZGVzaWduYXRlIGVhY2ggY293IGFzIGEgdHJ1dGggdGVsbGVyIG9yIGEgbGlhciBpbiBhIG1hbm5lciB0aGF0IGlzIGNvbnNpc3RlbnQgd2l0aCB0aGUgZmlyc3QgQSBlbnRyaWVzIGluIEZKJiMzOTtzIGxpc3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycywgTiBhbmQgTS48XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi4xK006IEVhY2ggbGluZSBpcyBvZiB0aGUgZm9ybSAmcXVvdDt4IHkgTCZxdW90OyBvciAmcXVvdDt4IHkgVCZxdW90OywgZGVzY3JpYmluZyBhIHN0YXRlbWVudCBtYWRlIGJ5IGNvdyB4IGFib3V0IGNvdyB5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBUaGUgbWF4aW11bSB2YWx1ZSBvZiBBIHN1Y2ggdGhhdCB0aGUgZmlyc3QgQSBlbnRyaWVzIGluIEZKJiMzOTtzIGxpc3QgY2FuIGJlIGNvbnNpc3RlbnQgd2l0aCBzb21lIGFzc2lnbm1lbnQgb2YgJnF1b3Q7dHJ1dGggdGVsbGVyJnF1b3Q7IG9yICZxdW90O2xpYXImcXVvdDsgdG8gdGhlIE4gY293cy48XC9wPlxyXG4iLCJoaW50IjoiPHA+U3RhdGVtZW50cyAxIGFuZCAzIGNhbm5vdCBib3RoIGJlIHNhdGlzZmllZCBhdCB0aGUgc2FtZSB0aW1lLCBidXQgc3RhdGVtZW50cyAxIGFuZCAyIGNhbiBiZSwgaWYgd2UgbGV0IGNvd3MgMS4uMyB0ZWxsIHRoZSB0cnV0aCBhbmQgY293IDQgYmUgYSBsaWFyLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==