Graph Marathon

Cho đồ thị có hướng \(G=(V,E)\) gồm \(N\) đỉnh và \(M\) cung, \(s\) và \(t\) là hai đỉnh của đồ thị \(G\). Một dãy các đỉnh \(P=\langle p_0=s, p_1, p_2, \dots, p_k=t \rangle\) sao cho \((p_{i_1}, p_i) \in E\), được gọi là 1 đường đi từ \(s\) đến \(t\). Một đường đi đơn giản (còn gọi là đường đi đơn) nếu tất cả các đỉnh trên đường đi đôi một khác nhau.
Biết rằng tồn tại ít nhất một đường đi từ s tới t, hãy chỉ ra đường đi đơn có thứ tự từ điển nhỏ nhất.

Input

• Dòng đầu chứa các số nguyên \(N\), \(M\), đỉnh xuất phát \(s\), đỉnh cần đến \(t\).
• \(M\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u,v\) \((1 \leq u,v \leq N)\), thể hiện cho 1 cung nối từ đỉnh \(u\) đến đỉnh $v trong đồ thị.

Output

• Ghi ra trên một dòng các đỉnh theo đúng thứ tự trên đường đi tìm được, bắt đầu từ đỉnh \(s\), kết thúc ở đỉnh \(t\) theo thứ tự từ điển nhỏ nhất.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3, M \leq 10^4\)
• Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5, M \leq 10^6\)

Example

8 12 1 8
1 2
1 3
2 3
2 4
3 1
3 5
3 7
4 6
6 2
6 8
7 8
7 6 

1 2 3 7 6 8

Khu vực SAN ANDREAS có \(N\) ngôi nhà và \(M\) đường giao thông một chiều. Mỗi con đường kết nối trực tiếp giữa 2 ngôi nhà. Các ngôi nhà được đánh số từ \(1\) tới \(N\). CJ đang chuẩn bị thanh toán nhóm BALLAS ở một ngôi nhà trong khu vực, và sẽ bắt đầu tại nhà của CJ. Nhà của CJ có chỉ số là \(s\), nhà của nhóm BALLAS có chỉ số là \(t\). Một đường đi gọi là đường đi đơn nếu trong quá trình đi từ nhà CJ tới nhà của nhóm BALLAS, tất cả ngôi nhà đi qua nhiều nhất một lần. Và tồn tại ít nhất một đường đi từ \(s\) tới \(t\) (vì thế CJ mới có thể đi thanh toán được).

Hãy tìm cho CJ đường đi đơn ngắn nhất để CJ nhanh chóng thanh toán nhóm BALLAS càng nhanh càng tốt (CJ còn nhiều việc chưa giải quyết xong). Nếu có nhiều đường đi đơn ngắn nhất, thì chỉ ra đường đi có thứ tự từ điển nhỏ nhất trong số đó.

Input

• Dòng đầu tiên chứa 4 số nguyên dương \(N,M,s,t \ (1 \leq s, t \leq N, s \ne t)\).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v \ (1 \leq u, v \leq N, u \ne v)\) thể hiện có đường đi một chiều nối từ ngôi nhà \(u\) tới ngôi nhà \(v\) trong khu vực.

Output

• Ghi ra trên một dòng các ngôi nhà theo đúng thứ tự trên đường đi ngắn nhất tìm được, bắt đầu từ ngôi nhà \(s\), kết thúc ở ngôi nhà \(t\) theo thứ tự từ điển nhỏ nhất (Ví dụ \(10\) có thứ tự từ điển lớn hơn \(5\), \(5\) có thứ tự từ điển lớn hơn \(1\)).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3, M \leq 10^4\).
• Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5, M \leq 10^6\).

Example

8 12 1 8
1 3
3 5
7 6
1 2
2 4
2 3
3 1
3 7
6 8
4 6
6 2
7 8 

1 3 7 8

Sau khi thanh toán hết băng nhóm BALLAS, CJ đã tịch thu những nơi do băng BALLAS làm chủ. Là một trong những người đứng đầu nhóm GROVE STREET FAMILIES, nên CJ đã ra lệnh cho một số lính thăm dò về vùng đất bị thu hồi này. Sau khi thăm dò, thì CJ biết trong vùng có \(N\) ngôi nhà, đánh số từ \(1\) tới \(N\), và có \(M\) tuyến đường giao thông hai chiều nối trực tiếp hai ngôi nhà với nhau. Lúc này CJ ra lệnh cho một số lính quản lý vùng đã được thu hồi với các điều kiện sau:

• Mỗi ngôi nhà chỉ chịu quản lý của một lính của CJ.
• Tập hợp các ngôi nhà có thể kết nối được với nhau (bất kỳ hai ngôi nhà nào cũng có thể kết nối với nhau) thì cũng chỉ chịu quản lý bởi một lính của CJ.
• Định nghĩa ngôi nhà \(u\) với ngôi nhà \(v\) kết nối được với nhau là tồn tại một đường đi giữa hai ngôi nhà \(u\) và \(v\), tức là tồn tại dãy các ngôi nhà \(P=⟨u = p_0 , p_1 ,…, p_k = v⟩\) sao cho \(∀i:1 \lt i \leq k\) thì tồn tại tuyến đường trực tiếp giữa hai ngôi nhà \(p_i−1\) và \(p_i\) trong khu vực.
• Số lính quản lý là ít nhất.

Yêu cầu: hãy tìm số lính quản lý thoả mãn các điều kiện của CJ, và chỉ ra rõ ra những ngôi nhà mà từng lính quản lý. Nếu có nhiều cách quản lý, chỉ ra một cách bất kì.

Input

• Gồm \(M+1\) dòng:
  • Dòng đầu tiên chứa 2 số nguyên dương \(N, M\).
  • \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) thể hiện có tuyến đường hai chiều nối trực tiếp từ ngôi nhà \(u\) tới ngôi nhà \(v\) trong vùng.

Output

• Gọi \(K\) là số đàn em quản lý thoả mãn các điều kiện của CJ. Ghi ra \(K+1\) dòng:

  • Dòng đầu tiên ghi ra số nguyên dương \(K\).
  • \(K\) dòng tiếp theo, dòng thứ \(i\) ghi ra số đầu tiên là số \(X\) - số ngôi nhà do lính \(i\) quản lý, \(X\) số tiếp theo là số hiệu ngôi nhà do lính \(i\) quản lý.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10 ^ 3, M \leq 10 ^ 4\).
• Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10 ^ 5, M \leq 10 ^ 6\).

Example

12 10
1 4
2 3
3 6
4 5
6 7
8 9
8 10
9 11
11 8
11 12 

3
3 1 4 5 
4 2 3 6 7 
5 8 9 10 11 12

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à \(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

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 

4
8 9 10 11

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. Trước đó, nhóm Los Santos Vagos tấn công để chiếm lấy vùng của Grove Street Families nhưng thất bại. Và nhóm của CJ đã quyết định đáp trả, phản công ngược lại nhóm Los Santos Vagos.

Sau khi thăm dò địa thế của đối phương, thì vùng ở Los Santos Vagos 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 hai chiều nối trực tiếp giữa hai căn cứ. CJ muốn nhắm, tìm ra các điểm trọng yếu của đối phương để đối phó. Điểm trọng yếu là những điểm khi mà bị nhóm CJ chặn, chiếm lấy thì những căn cứ mà điểm này đến được sẽ bị chia ra ít nhất hai phần và hai căn cứ thuộc hai phần khác nhau bất kì để không thể đi đến nhau được, và nhóm Los Santos sẽ nhanh bị suy yếu do không thể hỗ trợ lẫn nhau.

Ví dụ bản đồ căn cứ của Los Santos Vagos như trên, khi chiếm lấy điểm \(3\) thì tập các căn cứ tới điểm \(3\) là (\(6\), \(4\), \(2\), \(5\), \(1\)) bị chia ra \(3\) phần: (\(6\), \(4\)), (\(2\)) và (\(5\), \(1\)) và bất kỳ \(2\) căn cứ thuộc \(2\) trong \(3\) phần khác nhau bất kì, như \(6\) và \(2\), đều không thể tới được với nhau, nên điểm \(3\) là điểm trọng yếu. Điểm \(4\) cũng là điểm trọng yếu vì tập các căn cứ tới điểm \(4\) là (\(6\), \(2\), \(3\), \(1\), \(5\)) bị chia ra là (\(6\)), (\(2\), \(3\), \(1\), \(5\)). Còn các điểm \(1\), \(2\), \(5\), \(6\) không phải là các điểm trọng yếu.

Yêu cầu: Hãy chỉ ra cho CJ tất cả các điểm trọng yếu trên.

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ố tuyến đường hai chiều
  • \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u_i\) và \(v_i\) thể hiện có tuyến đường hai chiều nối từ căn cứ \(u_i\) tới căn cứ \(v_i\)

Output

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

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3, M \leq 3.10^3\)
• Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5, M \leq 3.10^5\)

Example

6 6
1 3
1 5
2 3
3 4
3 5
4 6 

2
3 4

Sau khi đánh bại được Los Santos Vagos, thì nhóm CJ cũng tịch thu hẳn vùng đất của đối phương. Bây giờ, CJ sẽ xây dựng lại trật tự cũng như tập trung vài lực lượng chính vào vùng đất này. Ở vùng có \(N\) căn cứ và \(M\) tuyến đường hai chiều nối trực tiếp hai căn cứ, các căn cứ được đánh số từ \(1\) tới \(N\), và các tuyến đường cũng được đánh số từ \(1\) tới \(M\). CJ cử vài lực lượng quản lý các căn cứ và quyết định cử thêm người để canh gác những con đường. CJ đặc biệt quan tâm tới các con đường mà CJ cho con đường đó là rất quan trọng.

Tuyến đường quan trọng, theo định nghĩa của CJ là những tuyến đường mà khi gặp sự cố nguy hiểm (có thể bị phá hoặc bị chiếm) thì tập hợp các căn cứ mà có thể thông qua tuyến đường này thì sẽ bị chia thành hai phần và bất kì \(2\) căn cứ nào thuộc hai tập khác nhau đều không thể qua lại, yểm trợ nhau và tình thế của nhóm Grove Street Families (nhóm của CJ) sẽ gặp nguy hiểm.

Ví dụ bản đồ căn cứ của Los Santos Vagos (bây giờ đã là của Grove Street Families) như trên, khi tuyến đường \(4 - 3\) gặp sự cố nguy hiểm thì tập các căn cứ có thể thông qua tuyến đường \(4 - 3\) là (\(6\), \(4\), \(2\), \(3\), \(5\), \(1\)) bị chia ra \(2\) phần: (\(6\), \(4\)) và (\(2\), \(3\), \(5\), \(1\)) và bất kỳ \(2\) căn cứ thuộc \(2\) phần khác nhau, như \(6\) và \(2\), đều không thể qua lại, yểm trợ nhau, nên \(4 - 3\) là tuyến đường quan trọng. Tuyến đường \(4 - 6\) cũng là tuyến đường quan trọng. Và tuyến đường \(1 - 5\) không phải là tuyến đường quan trọng.

Yêu cầu: Hãy chỉ ra cho CJ tất cả các tuyến đường quan trọng trên.

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ố tuyến đường hai chiều
  • \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u_i\) và \(v_i\) thể hiện có tuyến đường hai chiều nối từ căn cứ \(u_i\) tới căn cứ \(v_i\)

Output

• Ghi ra hai dòng:
  • Dòng đầu tiên ghi số \(K\) là số tuyến đường quan trọng.
  • Dòng tiếp theo là ghi ra số hiệu của \(K\) tuyến đường quan trọng tìm được theo thứ tự tăng dần.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3, M \leq 3.10^3\)
• Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5, M \leq 3.10^5\)

Example

6 6
1 3
1 5
2 3
3 4
3 5
4 6 

3
3 4 6

CJ đang cùng Sweet - trùm băng nhóm Grove Street Families, đồng thời cũng là anh trai CJ, cùng nhau đi nhiều nơi khác của vùng San Andreas. Trên đường đi, CJ và Sweet phát hiện được vùng đất mới mà chưa ai sinh sống ở đó, mà địa thế rất có lợi cho nhóm, nên CJ và Sweet đã quyết định khai phá, xây dựng lực lượng hùng mạnh ở đây. Sau mấy ngày liền, thì đã có \(N\) căn cứ nhỏ, các căn cứ được đánh số theo thứ tự từ \(1\) tới \(N\) và \(M\) tuyến đường hai chiều kết nối trực tiếp giữa hai căn cứ, đánh số từ \(1\) tới \(M\). Định nghĩa căn cứ \(u\) có thể qua lại với căn cứ \(v\) nếu tồn lại một số đường đi từ \(u\) tới \(v\), tức là tồn tại dãy \(P = 〈u = p_1, p_2, …, p_k = v〉\) sao cho \(\forall i: 1 < i \leq k\) thì tồn tại tuyến đường nối trực tiếp giữa hai căn cứ \(p_{i-1}\) và \(p_i\).

Bây giờ, CJ và Sweet đang bàn bạc để khoanh vùng một số căn cứ nhỏ làm khu căn cứ trung tâm, để tạo một lực lượng khá mạnh ở đây, tiện cho chiến lược phòng thủ khi bị tấn công. CJ và Sweet tìm khu chứa nhiều căn cứ nhất có thể sao cho bất kỳ \(2\) căn cứ nhỏ nào cũng có thể qua lại với nhau, và lỡ không may một trong các căn cứ trong khu vực đấy có bị đánh chiếm, thì các căn cứ còn lại vẫn có thể qua lại, yểm trợ nhau.

Ví dụ: Bản đồ các căn cứ của CJ và Sweet như trên, xét khu vực chứa các căn cứ (\(1\), \(3\), \(5\)). Khu vực ấy nếu căn cứ \(3\) gặp nguy hiểm thì căn cứ \(1\) và \(5\) vẫn có thể qua lại, yểm trợ nhau. Tương tự, nếu khu vực \(1\) hoặc \(5\) gặp nguy hiểm thì hai căn cứ còn lại vẫn có thể qua lại, yểm trợ nhau.

Yêu cầu: Hãy chỉ ra cho CJ và Sweet khu căn cứ trung tâm tìm được. Nếu có nhiều khu như vậy, chỉ ra một khu 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ố tuyến đường hai chiều
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u_i\) và \(v_i\) thể hiện có tuyến đường hai chiều nối từ căn cứ \(u_i\) tới căn cứ \(v_i\)

Output

• Ghi ra hai dòng:
• Dòng đầu tiên ghi ra số \(K\) là số căn cứ lớn nhất trong khu căn cứ trung tâm tìm được.
• Dòng thứ hai ghi ra số hiệu của \(K\) căn cứ lớn nhất trong khu căn cứ trung tâm tìm được theo thứ tự tăng dần.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3, M \leq 11.10^2\)
• Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5, M \leq 11.10^4\)

Example

6 6
1 3
1 5
2 3
3 4
3 5
4 6  

3
1 3 5

Trong một lần CJ làm nhiệm vụ thanh trường ngôi nhà nhỏ của nhóm Vagos (mới thành lập lại) thì đã cứu thoát được một cô gái tên là Denise. Denise rất biết ơn CJ, và hẹn một ngày nào đó sẽ cùng CJ dạo quanh vùng Los Santos, và tỏ lời cảm ơn tới CJ.

Ở vùng Los Santos có \(N\) chốt, được đánh số từ \(1\) tới \(N\) và \(M\) con đường có các quang cảnh nổi tiếng hai chiều nối giữa hai chốt, cũng được đánh số từ \(1\) tới \(M\). Một ngày, đúng như lời hẹn, CJ và Denise cùng nhau dạo quanh phố. Nhưng vì hai người không có nhiều thời gian, và còn nhiều việc khác nữa, mà muốn đi hết tất cả các con đường để ngắm cảnh, chụp hình, …. nên CJ và Denise quyết định tạo một hành trình xuất phát từ một chốt, sao cho mỗi con đường đi qua duy nhất một lần (không đi một con đường hai lần và không bỏ qua con đường nào) và quay trở lại điểm xuất phát.

Yêu cầu: Biết rằng tồn tại ít nhất một hành trình thoả mãn quyết định của CJ và Denise. Hãy chỉ ra một hành trình trên.

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ố chốt và số con đường hai chiều.
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u_i\) và \(v_i\) thể hiện có đường hai chiều nối hai chốt \(u_i\) và \(v_i\) và \(u_i \neq v_i\).

Output

• Ghi ra \(M + 1\) số là số hiệu của các chốt theo thứ tự hành trình trên một dòng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\), \(M \leq 10^4\)
• Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5\), \(M \leq 4.10^5\)

Example

5 9 
1 2 
1 3 
2 3 
2 4 
2 5 
3 4 
3 5 
4 5 
4 5 

1 3 5 4 5 2 4 3 2 1

Một ngày, CJ cảm thấy lâu rồi chưa tới chơi nhà của tất cả các người quen của mình ở vùng Los Santos, nên đã quyết định đi dạo quanh, thăm tất cả người quen trong vùng, rồi trở lại tiếp tục công việc của mình.

Vùng Los Santos có \(N\) ngôi nhà có người quen, đánh số từ \(1\) tới \(N\), và \(M\) con đường hai chiều, giữa hai ngôi nhà có không quá một con đường nối trực tiếp. CJ còn khá nhiều việc chưa giải quyết nên xuất phát từ một ngôi nhà, đi qua hết tất cả ngôi nhà còn lại, mỗi ngôi nhà tới đúng một lần, và trở về ngôi nhà xuất phát (không ngôi nhà nào đi hai lần trừ ngôi nhà xuất phát, không bỏ qua ngôi nhà nào).

Yêu cầu: Biết rằng tồn tại ít nhất một hành trình như vậy. Hãy chỉ ra cho CJ một hành trình trên.

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ố ngôi nhà có người quen và số con đường hai chiều \((M \leq \dfrac{N . (N-1)}{2})\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u_i\) và \(v_i\) thể hiện có đường hai chiều nối hai ngôi nhà \(u_i\) và \(v_i\) và \(u_i \neq v_i\)

Output

• Ghi ra \(N + 1\) số là số hiệu của các ngôi nhà theo thứ tự hành trình trên một dòng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 30\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \leq 2.10^3\)
• Subtask \(3\) (\(20\%\) số điểm): \(N \leq 4.10^3\)
  (Đẩy giới hạn test cao hơn cho có màu :V)

5 8 
1 2 
1 3 
3 2 
2 4 
5 3 
3 5
4 1 
5 4 

1 2 3 5 4 1

Một ngày, OG Loc đã mời CJ dự một buổi tiệc rap của anh ta. Và hôm nay buổi tiệc sẽ diễn ra, nhưng CJ vì mải mê công việc, mà khi nhìn vào đồng hồ và lịch thì … CJ mới chợt nhớ ra về bữa tiệc của OG Loc. Mà còn khoảng \(2\) tiếng nữa là buổi tiệc rap của OG Loc sẽ diễn ra.

CJ nhìn vào bản đồ trong vùng. Bản đồ đấy gồm \(N\) ngôi nhà, đánh số từ \(1\) tới \(N\) và \(M\) con đường hai chiều nối hai ngôi nhà. Ngôi nhà của CJ có số hiệu là \(s\), ngôi nhà có bữa tiệc của OG Loc có số hiệu là \(t\). Vì không muốn tới trễ nên CJ quyết định tìm đường đi ngắn nhất từ nhà của mình tới buổi tiệc tại ngôi nhà của OG Loc và sẽ di chuyển theo đường đi đó.

Input

• Gồm \(M + 1\) dòng:
• Dòng đầu tiên chứa bốn số nguyên dương \(N\), \(M\), \(s\), \(t\) \((1 \leq s, t \leq N, s \neq t)\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số \(u_i\), \(v_i\), \(c_i\) thể hiện có đường hai chiều nối hai ngôi nhà \(u_i\) và \(v_i\), và độ dài là \(c_i\) (\(u_i \neq v_i\)).

Output

• Ghi ra hai dòng:
• Dòng đầu tiên ghi ra độ dài đường đi ngắn nhất.
• Dòng thứ hai là số hiệu trên đường đi ngắn nhất tìm được theo thứ tự di chuyển, bắt đầu từ \(s\) và kết thúc ở \(t\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3, M \leq 2.10^3\)
• Subtask \(2\) (\(70\%\) số điểm): \(N \leq 10^5, M \leq 2.10^5\)

Example

3 3 1 3
1 2 3
1 3 5
2 3 1 

4
1 2 3

Bản đồ vùng Los Santos có \(N\) căn cứ, được đánh số từ \(1\) tới \(N\) và \(M\) tuyến đường hai chiều, đánh số từ \(1\) tới \(M\). Mỗi tuyến đường chỉ chịu đựng số người đi qua cùng lúc nhất định, nếu quá số người đi qua cùng một lúc sẽ bị hư hỏng và không thể đi qua được.

CJ vừa mới khảo sát tình hình ở các khu vực trong vùng Los Santos và nhận thấy rằng ở căn cứ \(t\) vẫn còn yếu thế nên CJ đã huy động thêm lực lượng, xuất phát từ căn cứ \(s\), và đến căn cứ \(t\) để căn cứ \(t\) được tăng lên sức mạnh phòng thủ cũng như tấn công.

Nhưng tất cả tuyến đường đều bị giới hạn số người đi qua cùng lúc, nên CJ phải tính toán xem tối đa bao nhiêu người có thể đi từ \(s\) tới \(t\) và hành trình đi tương ứng như thế nào. Biết rằng tất cả lực lượng tập hợp lại và đi theo một nhóm và không tách rời, vì tách rời có khả năng bị nhóm khác dòm ngó và tiêu diệt.

Yêu cầu: Tìm số người lớn nhất mà CJ có thể tính toán và di chuyển lực lượng và chỉ ra hành trình tương ứng. Nếu có nhiều hành trình, in ra một hành trình bất kì.

Input

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

• Dòng thứ nhất chứa bốn số nguyên dương \(N\), \(M\), \(s\), \(t\) \((1 \leq s, t \leq N, s \neq t)\).

• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên dương \(u_i\), \(v_i\) và \(c_i\) thể hiện có tuyến đường nối trực tiếp giữa \(u_i\) và \(v_i\) và sức chịu đựng là \(c_i\) \((c_i \leq 10^9, u_i \neq v_i)\).

Output

• Gồm hai dòng:

• Dòng thứ nhất là số người lớn nhất mà CJ có thể tính toán và di chuyển lực lượng.

• Dòng thứ hai là số hiệu của các căn cứ theo thứ tự hành trình, bắt đầu từ căn cứ \(s\), và kết thúc ở căn cứ \(t\).

Scoring

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

Example

6 6 1 6
2 5 15
6 5 9
2 6 16
4 1 17
3 1 14
4 6 7 

7
1 4 6

Sau bao nhiêu ngày tháng xây dựng ở vùng đất mới, thì CJ đã cử vài lực lượng cùng anh tới khu vực đó để khảo sát tình hình làm việc cũng như địa thế. CJ đặt biệt quan tâm đến sức mạnh và sự hỗ trợ của đồng đội, nên đã khảo sát như sau:

• Ở vùng đó có \(N\) căn cứ, được đánh số từ 1 tới \(N\) và \(M\) tuyến đường hai chiều, được đánh số từ \(1\) tới \(M\).
• Lực lượng của CJ sẽ tìm độ dài đường đi ngắn giữa Q cặp căn cứ \(s\), \(t\) bất kì do CJ muốn xem xét để làm kết quả của cuộc khảo sát, rồi sau đó về họp bàn sau.
• Định nghĩa căn cứ \(s\) có thể đi tới căn cứ \(t\) là tồn tại một đường đi từ \(s\) tới \(t\), tức là tồn tại dãy các căn cứ \(P=⟨s=p_0,p_1,...,p_k=t⟩\) sao cho \(\forall i:1 \leq i \leq k\) thì tồn tại tuyến đường trực tiếp giữa hai căn tứ \(p_{i-1}\) và căn cứ \(p_i\).

Yêu cầu: Với mỗi cặp căn cứ \(s\), \(t\) do CJ chọn, tìm đường đi ngắn nhất giữa hai căn cứ \(s\) và \(t\).

Input

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

• Dòng thứ nhất chứa ba số nguyên dương \(N\), \(M\), \(Q\) thể hiện số căn cứ, số con đường và số cặp căn cứ muốn xem xét.

• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên dương \(u_i\), \(v_i\) và \(c_i\) thể hiện có tuyến đường nối trực tiếp giữa \(u_i\) và \(v_i\) và có độ dài là \(c_i\) \((c_i \leq 10^9, u_i \neq v_i)\).
• \(Q\) dòng cuối cùng, dòng thứ \(i\) chứa hai số \(s_i\) và \(t_i\) thể hiện cặp căn cứ \(s_i\), \(t_i\) mà CJ muốn xem xét \((s_i \neq t_i)\).

Output

• Gồm \(Q\) dòng, dòng thứ \(i\) là đường đi ngắn nhất giữa cặp căn cứ \(s_i\), \(t_i\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^2, M \leq 10^3, Q \leq 5 \times 10^2\).
• Subtask \(2\) (\(25\%\) số điểm): \(N \leq 3 \times 10^2, M \leq 2 \times 10^4, Q \leq 2 \times 10^2\).
• Subtask \(3\) (\(50\%\) số điểm): \(N \leq 4 \times 10^2, M \leq 35 \times 10^3, Q \leq 35 \times 10^3\).

Example

6 6 2
3 1 2
5 2 1
6 5 9
5 1 4
5 3 6
4 6 1
4 5
3 2 

10
7

Sau khi làm nhiệm vụ cho nhóm C.R.A.S.H, thì giờ đây CJ đã không còn làm được gì, cả không thể về lại nơi cũ vì sẽ bị nhóm này truy sát. Trong lúc CJ đang đi quanh quẩn nơi đây thì vô tình gặp Catalina và cô gái này rất là hám tiền. CJ và Catalina bắt tay với nhau, và Catalina nhờ CJ giúp một công việc: Cướp hết ngân hàng nhỏ ở các khu vực nông thôn.

Ở vùng nông thôn San Andreas có \(N\) địa điểm, trong đó có \(K\) địa điểm là ngân hàng, đánh số từ \(1\) tới \(N\), và \(M\) con đường hai chiều, đánh số từ \(1\) tới \(M\), con đường thứ \(i\) có độ dài là \(L_{i}\). Catalina muốn CJ tìm đường đi sao cho xuất phát từ một ngân hàng, cướp hết tất cả \(K\) ngân hàng, mỗi con đường và một địa điểm có thể được đi qua nhiều lần, và độ dài đường đi là ngắn nhất có thể. Đảm bảo hai ngân hàng khác nhau bất kì đều có đường đi.

Yêu cầu: Hãy tìm ra cho CJ và Catalina độ dài đường đi ngắn nhất trên.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(N,M,K\) thể hiện số địa điểm, số con đường hai chiều, số ngân hàng.
• Dòng tiếp theo chứa \(K\) số \(a_{1},a_{2},…,a_{K}\) là số hiệu của các địa điểm là ngân hàng.
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên dương \(u_{i},v_{i}, L_{i}\) thể hiện có đường nối trực tiếp \(u_{i},v_{i}\) và độ dài là \(L_{i}\).

Output

• Ghi ra độ dài đường đi ngắn nhất.

Constraints

• \(1 \leq N \leq 10^{5}\), \(1 \leq M \leq 2.10^{5}\)
• \(1 \leq K \leq 18\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^{3}\), \(M \leq 2.10^{3}\), \(K \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^{5}\), \(M \leq 2.10^{5}\), \(K \leq 10\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

6 6 2
1 4 
3 2 1
5 4 3
5 1 1
1 2 7
3 5 3
6 1 1 

4

Một ngày, Sweet nổi hứng lên, và đi ra khiêu chiến với nhóm Ballas mà CJ không hề biết gì. Tới khi Sweet bị trọng thương thì mới báo CJ biết, và CJ tới cứu viện. Nhưng khi đó cảnh sát tới, và tất cả mọi người chạy trốn hết trừ Sweet và CJ. Sweet thì vào tù, còn CJ thì bị nhóm cảnh sát Frank Tenpenny (C.R.A.S.H) bắt cóc, và đưa đến vùng cao, hẻo lánh ở Whetstone.

CJ bị nhóm C.R.A.S.H bắt phải làm nhiệm vụ: là tìm kẻ The Imforman để thanh toán. Và CJ phải làm, vì nếu không sẽ bị nhóm tiêu diệt. Được biết, ở vùng Whetstone có \(N\) đỉnh núi, được đánh số từ \(1\) tới \(N\), đỉnh núi \(i\) có độ cao là \(h[i]\), giữa hai đỉnh khác nhau bất kỳ đều có một đường đi. CJ đang ở đỉnh núi thứ \(s\), và The Imforman đang ở đỉnh núi thứ \(t\).

Nếu tồn tại con đường từ đỉnh núi \(u\) tới đỉnh núi \(v\), tức là tồn tại dãy các đỉnh núi \(P=⟨u=p0,p1,...,pk=v⟩\) sao cho \(\forall i:1 \leq i \leq k\) thì tồn tại tuyến đường trực tiếp giữa hai đỉnh núi \(p_{i−1}\) và \(p_i\), thì định nghĩa độ nguy hiểm trên đường đi từ \(u\) tới \(v\) là \(max(|h[p_1] - h[p_0]|, |h[p_2] - h[p_1]|, …, |h[p_k] - h[p_{k-1}]|)\).

Vì CJ muốn an toàn cho mình khi di chuyển nên hãy chỉ ra cho CJ độ nguy hiểm nhỏ nhất và hành trình trên đường đi tương ứng từ \(s\) tới \(t\). Nếu có nhiều đường đi, chỉ ra một hành trình trên đường đi bất kỳ.

Input

• Gồm hai dòng:

• Dòng thứ nhất chứa ba số nguyên dương \(N\), \(s\), \(t\). \((1 \leq s, t \leq N, s \neq t)\)

• Dòng thứ hai chứa \(N\) số nguyên dương \(h[1], h[2], … h[N]\), với \(h[i]\) là độ cao của đỉnh núi \(i\) \((1 \leq i \leq N, h[i] \leq 10^9)\).

Output

• Gồm hai dòng:

• Dòng thứ nhất là độ nguy hiểm nhỏ nhất mà CJ trên con đường tìm được.

• Dòng thứ hai là số hiệu của các đỉnh núi theo thứ tự hành trình, bắt đầu từ đỉnh \(s\), và kết thúc ở đỉnh \(t\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \leq 10^2\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^3\).
• Subtask \(3\) (\(50\%\) số điểm): \(N \leq 10^4\).

Example

6 1 6
7 7 1 1 3 1 

4
1 5 6

Sau khi cướp hết ngân hàng, thì Catalina cùng Claude đã đi tới Liberty City. Chỉ còn CJ ở lại. CJ giờ cũng chẳng biết làm gì, và đi dạo đâu đó chơi. Trong lúc đi dạo, vô tình gặp ông The Truth. Và hai người bắt tay với nhau làm bạn, và cùng nhau tới thành phố San Fierro làm ăn với chiếc xe buýt của ông. Trong lúc đi thì ông chợt nhận ra là ở thành phố này chủ yếu là đường hầm, ông thì chưa đo độ cao chiếc xe ?!!. Và ông đã đưa cho CJ tấm bản đồ San Fierro.

Thành phố San Fierro có \(N\) địa điểm, đánh số từ \(1\) tới \(N\), và \(M\) con đường có hầm, được đánh số từ \(1\) tới \(M\), con đường thứ \(i\) có độ dài là \(L_{i}\), độ cao giới hạn là \(H_{i}\). Xe của ông hiện tại ở địa điểm \(s\), và muốn tới địa điểm \(t\). Và ông quyết định nhờ CJ tìm đường đi mà độ cao đạt được là lớn nhất có thể để đi qua. Trong các đường đi có cùng độ cao lớn nhất, thì ông muốn lấy đường đi ngắn nhất có thể.

Hãy chỉ ra cho CJ con đường thoả mãn điều kiện của ông The Truth. Nếu có nhiều đường đi thoả mãn, in ra một đường đi bất kỳ.

Input

• Dòng đầu tiên chứa bốn số nguyên dương \(N,M,s,t\) (\(1 \leq s,t \leq N, s \neq t\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên dương \(u_{i},v_{i}, L_{i},H_{i}\) (\(1 \leq u_{i},v_{i} \leq N, u_{i} \neq v_{i},1 \leq L_{i},H_{i} \leq 10^{9}\)).

Output

• Gồm 2 dòng:
• Dòng đầu tiên ghi ra độ cao lớn nhất có thể.
• Dòng thứ hai ghi ra số hiệu trên đường đi tương ứng có độ dài nhỏ nhất theo thứ tự hành trình, bắt đầu từ \(s\) và kết thúc tại \(t\).

Constraints

• \(1 \leq N \leq 10^{5}\), \(1 \leq M \leq 2.10^{5}\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^{3}\), \(M \leq 2.10^{3}\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

6 6 4 3
1 2 7 10
5 3 3 7
5 1 7 7
5 4 7 3
2 5 5 7
3 6 6 8 

3
4 5 3

Khi tới San Fierro, thì CJ muốn đi du lịch quanh thành phố cho thoả thích, với lại để thăm quan nơi đây. CJ có được tấm bản đồ thành phố mà trước ông The Truth có đưa cho anh.

Thành phố San Fierro có \(N\) địa điểm nổi tiếng mà CJ muốn đến, được đánh số từ \(1\) tới \(N\), và \(M\) con đường hai chiều, được đánh số từ \(1\) tới \(M\). Vì CJ chỉ có \(4\) ngày nghỉ ngơi nên CJ quyết định lập hành trình du lịch gồm \(4\) địa điểm nổi tiếng khác nhau \(A_{1},A_{2},A_{3},A_{4}\) sao cho có đường nối trực tiếp giữa \(A_{1}\) với \(A_{2}\), \(A_{2}\) với \(A_{3}\), \(A_{3}\) với \(A_{4}\), và mỗi địa điểm trong \(4\) địa điểm được chọn thăm đúng một lần và không đi tới các địa điểm nổi tiếng khác mà không nằm trong danh sách \(4\) điểm được chọn.

Vì CJ muốn được thoải mái, sảng khoái tinh thần nhất có thể để làm việc, nên CJ đã tham khảo trên bản đồ tất cả các địa điểm nổi tiếng trên. Và mỗi địa điểm sẽ cho CJ độ sảng khoái tinh thần là \(C_{i}\). Hãy giúp CJ lập ra hành trình sao cho tổng độ sảng khoái tinh thần là cao nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N,M\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(C_{1},C_{2},…,C_{N}\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(u_{i},v_{i}\).

Output

• Gồm 2 dòng:
• Dòng đầu tiên ghi ra tổng độ sảng khoái tinh thần cao nhất có thể.
• Dòng thứ hai ghi ra số hiệu của \(4\) địa điểm \(A_{1},A_{2},A_{3},A_{4}\) theo thứ tự hành trình. Dữ liệu đảm bảo CJ có thể chọn \(4\) địa điểm trên hành trình.

Constraints

• \(1 \leq N \leq 10^{5}\), \(1 \leq M \leq 3.10^{5}\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^{2}\), \(M \leq 3.10^{2}\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

6 6
7 8 1 1 7 1 
1 3
4 2
1 6
4 6
5 1
3 5 

17
2 4 6 1