Los Santos Vagos

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nhóm của CJ - tức là nhóm Grove Street Families và nhóm Los Santos Vagos trước giờ là kẻ thù của nhau, và bây giờ vẫn vậy. Và giờ nhóm Los Santos Vagos sẽ cố để chiếm lấy vùng của Grove Street Families mà trước đó CJ đã tịch thu từ Ballas. CJ thì đang tìm khu vực trọng điểm trong vùng để tập trung lực lượng chống trả nhóm Los Santos Vogas.

Trên bản đồ vùng của Grove Street Families có \(N\) điểm căn cứ, các căn cứ được đánh số theo thứ tự từ \(1\) tới \(N\), và \(M\) tuyến đường một chiều nối trực tiếp giữa hai căn cứ. Khu vực trọng điểm là khu có nhiều căn cứ nhất, sao cho bất kỳ hai căn cứ nào cũng có thể đi đến để yểm trợ cho nhau. Định nghĩa căn cứ \(u\) có thể đi tới căn cứ \(v\) là tồn tại một đường đi từ \(u\) tới \(v\), tức là tồn tại dãy các căn cứ \(P=⟨u=p_0,p_1,...,p_k=v⟩\) sao cho \(∀i:1\leq i \leq k\) thì tồn tại tuyến đường trực tiếp từ căn tứ \(p_{i−1}\) tới căn cứ \(p_i\).

Yêu cầu: Hãy tìm cho CJ khu vực trọng điểm trên. Nếu có nhiều khu vực trọng điểm như vậy, chỉ ra một khu vực bất kì.

Input

Gồm \(M + 1\) dòng:

  • Dòng đầu tiên chứa hai số nguyên dương \(N\), \(M\) thể hiện số căn cứ và số con đường một chiều.
  • \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u_i\)\(v_i\) thể hiện có đường một chiều nối từ căn cứ \(u_i\) tới căn cứ \(v_i\).

Output

  • Dòng đầu tiên ghi số \(K\) là số căn cứ lớn nhất trong khu vực trọng điểm tìm được.
  • Dòng tiếp theo là ghi ra số hiệu của \(K\) căn cứ trong khu vực trọng điểm theo thứ tự tăng dần.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N\leq10^3,M\leq2\times10^3\).
  • Subtask \(2\) (\(70\%\) số điểm): \(N\leq10^5,M\leq2\times10^5\).

Example

Test 1

Input
11 15
1 2
1 8
2 3
3 4
4 2
4 5
5 6
6 7
7 5
8 9
9 4
9 10
10 8
10 11
11 8 
Output
4
8 9 10 11

Bình luận

Không có bình luận nào.