SPOJ.com - Problem PBCGANGS

Problem hidden

|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PBCGANGS - Các băng đảng

Chicago những năm 1920 là 1 cuộc chiến giữa các găngxtơ.

Nếu 2 găngxtơ đã từng chạm mặt nhau thì họ có thể là bạn hoặc kẻ thù của nhau.

Các găngxtơ sống và chết theo quy tắc sau:

1. Bạn của bạn mình cũng là bạn mình.

2. Kẻ thù của kẻ thù của mình là bạn mình.

Hai găngxtơ cùng băng đảng khi và chỉ khi họ là bạn. Kal El là giám đốc sở cảnh sát Chicago. Bạn hãy giúp anh ấy tính số lượng lớn nhất có thể của các băng đảng khác nhau ở Chicago dựa vào tài liệu của sở về các lần gặp mặt của bọn chúng.

Input

Dòng đầu tiên chứa số nguyên N (2<=N<=1000) là số găngxtơ. Các găngxtơ được đánh số từ 1 đến N. Dòng thứ 2 chứa số nguyên M (1<=M<=5000) là số thông tin về các lần gặp mặt của các găngxtơ. M dòng tiếp theo là danh sách các thông tin đó. Mỗi thông tin nằm trong 1 dòng có dạng F p q hoặc E p q (1<=p,q<=N) với p q là số hiệu của 2 găngxtơ, nếu kí tự đầu tiên là F thì p và q là bạn, nếu là E thì p và q là kẻ thù.

Output

Chứa 1 số duy nhất là số lớn nhất các băng đảng.

Example

Input

F 1 4

Output

Submit solution!

Được gửi lên bởi:	bnta2
Ngày:	2010-12-04
Thời gian chạy:	0.100s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Ngôn ngữ cho phép:	Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED TCL
Nguồn bài:	...

hide comments

2016-07-13 18:18:40 THK6
DS thú vị thật :3

2016-05-11 14:27:49 xin Ä‘á»«ng quÃªn tÃ´i
Tham khảo thuật toán + code tại: http://yeulaptrinh.pw/146/pbcgangs-spoj/

2015-06-01 01:05:29 Stupid Dog
danh sách các lần gặp mặt sắp theo thứ tự thời gian chăng

2015-06-01 00:59:13 Stupid Dog
Giả sử (u,v) (v,k) (k,u) là thù, theo quy tắc thì (u,k) phải thành bạn do có chung kẻ thù là v, tương tự (v,k) phải thành bạn, do đó (u,v,k) thành bạn ??? Một lối sống rất nhân ái !!!

2015-03-31 06:04:34 Khanh Ninh
nối bạn lại(kẻ thù thì nối trung gian), rồi đếm miền liên thông là xong

2014-11-19 16:24:13 Change The World
thật đơn giản=))

2013-06-15 09:43:22 a;slkfjasl;fkj
có nhiều test nếu chỉ dựa trên 2 quy tắc thì vừa là bạn mình vừa là kẻ thù của mình @@

2013-04-02 11:35:02 ^.^
đúng rồi... cái này sử dụng DS là được

2013-01-27 17:32:32 Lai Manh Tuan
@ Nguyen Trong Dong:
3

Last edit: 2013-01-27 17:33:08

2012-07-05 14:52:44 2ez
test nay ra bn cac anh:
4
3
E 1 2
F 2 3
E 3 4

Giải bài trực tuyến

PBCGANGS - Các băng đảng