Duyệt đồ thị BFS-DFS - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Đường đi đẹp nhất	10 (p)	1.0s	256M
2	CSES - Building Roads \| Xây đường	10 (p)	1.0s	512M
3	Quản lý vùng BALLAS	10 (p)	1.0s	256M
4	Bảo vệ nông trang	10 (p)	1.0s	1023M
5	Nước lạnh	10 (p)	1.0s	256M
6	CJ Phản công	10 (p)	1.0s	256M
7	Los Santos Vagos	10 (p)	1.0s	256M
8	CEDGE	10 (p)	1.0s	256M
9	Liên thông	10 (p)	2.0s	256M
10	CSES - Strongly Connected Edges \| Cạnh của đồ thị liên thông mạnh	10 (p)	1.0s	512M
11	CSES - Dynamic Connectivity \| Liên thông động	10 (p)	1.0s	512M
12	Bài toán đếm đường đi trong đồ thị đơn có hướng(*)	10 (p)	2.0s	1023M

1. Đường đi đẹp nhất

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

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

Test 1

Input

Output

1 2 3 7 6 8

2. CSES - Building Roads | Xây đường

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

Byteland có $n$ thành phố, và $m$ con đường đường giữa chúng. Mục tiêu là xây dựng các con đường mới để có một tuyến đường giữa hai thành phố bất kỳ.

Nhiệm vụ của bạn là tìm ra số lượng đường tối thiểu cần thiết, đồng thời xác định những con đường nào nên được xây dựng.

Input

Dòng đầu vào đầu tiên có hai số nguyên $n$ và $m$: số lượng thành phố và con đường đường. Các thành phố được đánh số $1,2,\ldots,n$
Sau đó, có $m$ dòng mô tả các con đường. Mỗi dòng có hai số nguyên $a$ và $b$: có một đường giữa các thành phố đó
Một con đường luôn kết nối hai thành phố khác nhau, và có nhiều nhất một con đường giữa hai thành phố bất kỳ
Ràng buộc:
- $1 \leq n \leq 10^5$
- $1 \leq m \leq 2 \cdot 10^5$
- $1 \leq a, b \leq n$

Output

Đầu tiên in một số nguyên $k$: số lượng con đường cần thiết
Sau đó, in $k$ dòng mô tả các con đường mới. Bạn có thể in bất kỳ giải pháp hợp lệ nào

Example

Test 1

Input

4 2
1 2
3 4

Output

1
2 3

3. Quản lý vùng BALLAS

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

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

Test 1

Input

Output

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

4. Bảo vệ nông trang

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

Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân John muốn đặt người canh gác trên các ngọn đồi này. Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt 1 người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm $N (1 < N \leq 700)$ hàng và $M (1 \leq M \leq 700)$ cột. Mỗi phần tử của ma trận là độ cao $H_{ij}$ so với mặt nước biển $(0 \leq H_{ij} \leq 10000)$ của ô $(i,j)$. Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ.

Đỉnh đồi là $1$ hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ $X$ không quá $1$ và chênh lệch tọa độ $Y$ không quá $1$.

Input

Dòng 1: Hai số nguyên cách nhau bởi dấu cách: $N$ và $M$
Dòng 2 $\ldots$ N + 1: Dòng $i+1$ mô tả hàng $i$ của ma trận với $M$ số nguyên cách nhau bởi dấu cách: $H_{ij}$

Output

Một số nguyên duy nhất là số lượng đỉnh đồi.

Example

Test 1

Input

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0    
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

Output

5. Nước lạnh

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

Mùa hè oi ả ở Wisconsin đã khiến cho lũ bò phải đi tìm nước để làm dịu đi cơn khát. Các đường ống dẫn nước của nông dân John đã dẫn nước lạnh vào 1 tập $N$ nhánh (đánh số từ $1...N$) từ một cái bơm đặt ở chuồng bò.

Khi nước lạnh chảy qua các ống, sức nóng mùa hè sẽ làm nước ấm lên. Bessie muốn tìm chỗ có nước lạnh nhất để cô bò có thể tận hưởng mùa hè một cách thoải mái nhất.

Bessie đã vẽ sơ đồ toàn bộ các nhánh ống nước và nhận ra rằng nó là một đồ thị dạng cây với gốc là chuồng bò và ở các điểm nút ống thì có chính xác $2$ nhánh con đi ra từ nút đó. Một điều ngạc nhiên là các nhánh ống này đều có độ dài là $1$.

Cho bản đồ các ống nước, hãy cho biết khoảng cách từ chuồng bò tới tất cả các nút ống và ở các phần cuối đường ống.

"Phần cuối" của một đường ống, có thể là đi vào một nút ống hoặc là bị bịt, được gọi theo số thứ tự của đường ống. Bản đồ có $C$ nút ống, được mô tả bằng $3$ số nguyên: là "phần cuối" của ống $E_{i}$ và $2$ ống nhánh đi ra từ đó là $B_{1i}$ và $B_{2i}$. Đường ống số $1$ nối với chuồng bò; khoảng cách từ phần cuối của đường ống này tới chuồng bò là $1$.

Input

Dòng 1: 2 số nguyên cách nhau bởi dấu cách: $N$ và $C$
Dòng $2...C+1$: Dòng $i+1$ mô tả nút ống $i$ với ba số nguyên cách nhau bởi dấu cách: $E_{i},B_{1i}$, và $B_{2i}$.

Output

Dòng $1...N$: Dòng $i$ chứa $1$ số nguyên là khoảng cách từ chuồng tới "phần cuối" của ống thứ $i$.

Constraints

$3 \leq N \leq 99999$, $N$ lẻ
$1 \leq C \leq N$
$1 \leq E_{i} \leq N$
$2 \leq B_{1i}, B_{2i} \leq N$

Example

Test 1

Input

5 2
3 5 4
1 2 3

Output

Note

Dữ liệu ở trên mô tả bản đồ ống nước sau:
+-––––––-+
| Chuồng |
+-––––––-+
| 1
*
2 / \ 3
*
4 / \ 5
Ống 1 luôn cách chuồng 1 đoạn là 1. Ống 2 và 3 nối với ống 1 nên khoảng cách sẽ là 2. Ống 4 và 5 nối với ống 3 nên khoảng cách sẽ là 3.
```

6. CJ Phản công

Điểm: 10 (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. 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

Test 1

Input

Output

2
3 4

7. Los Santos Vagos

Điểm: 10 (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à $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

Output

4
8 9 10 11

8. CEDGE

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

Cho một cây (đồ thi liên thông vô hướng không chu trình) gồm $N$ nút. Các nút được đánh số từ 1 đến $N$.

Nhiệm vụ của bạn là tô màu các cạnh trên cây, sao cho với mỗi nút, không có hai cạnh bất kì kề với nút đó được tô cùng một màu. Trong các cách tô màu thỏa mãn, hãy tìm cách tô dùng ít màu phân biệt nhất.

Lưu ý: Nếu có nhiều cách tô dùng ít màu phân biệt nhất và thỏa mãn điều kiện, bạn có thể in ra một cách bất kì.

Input

Dòng đầu tiên gồm một số nguyên $N (2<N<10^5)$.
$N—1$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i$ và $b_i$ $(1<a_i,b_i<N)$ biểu diễn cạnh nối giữa nút $a_i$ và $b_i$.

Output

Dòng đầu tiên in ra một số nguyên $K$ là số lượng màu phân biệt ít nhất được dùng để tô.
$N—1$ dòng tiếp theo, dòng thứ $i$ in ra một số nguyên $c_i$ $(1<c_i<K)$ biểu diễn màu của cạnh thứ $i$ trong cách cho ban đầu.

Example

Test 1

Input

3
1 2
2 3

Output

2
1
2

Test 2

Input

Output

Test 3

Input

Output

9. Liên thông

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

Một quốc gia nọ có $N$ thành phố. Người ta đã xây dựng $M$ con đường một chiều để di chuyển giữa các thành phố. Quốc vương muốn đảm bảo rằng giữa hai thành phố bất kỳ, phải luôn tồn tại một cách di chuyển (trực tiếp hoặc gián tiếp) từ thành phố này đến thành phố kia. Bạn hãy kiểm tra xem ông có cần phải xây dựng các con đường mới không?

Input

Dòng đầu tiên chứa $1$ số nguyên dương $T$.
Tiếp theo là $T$ bộ dữ liệu, mỗi bộ dữ liệu gồm:
Dòng đầu chứa $2$ số nguyên $N,M$ là số thành phố và số con đường $1$ chiều.
Mỗi dòng trong $M$ dòng tiếp theo gồm $2$ số nguyên $u,v$ ($u \neq v$): người ta đã xây dựng con đường $1$ chiều từ $u$ đến $v$.

Output

Mỗi dòng là câu trả lời cho một bộ dữ liệu tương ứng: in ra YES nếu quốc vương cần xây thêm đường mới, NO nếu những con đường hiện tại đã thỏa mãn yêu cầu của ông.

Constraints

$1 \leq T \leq 5$
$1 \leq N,M \leq 10^{5}$
$1 \leq u,v \leq N$

Scoring

Subtask $1$ ($40\%$ số điểm): $N,M \leq 2000$.
Subtask $2$ ($60\%$ số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input

Output

NO
YES

Note

Trong bộ dữ liệu thứ hai, có $2$ con đường $1→2$ và $2→3$. Người ta không thể di chuyển từ thành phố $3$ đến thành phố $1$ với hai con đường này.

10. CSES - Strongly Connected Edges | Cạnh của đồ thị liên thông mạnh

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

Cho một đồ thị vô hướng, nhiệm vụ của bạn là định chiều mỗi cạnh để nhận được đồ thị có hướng liên thông mạnh.

Input

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ lần lượt là số đỉnh và số cạnh. Các đỉnh được đánh chỉ số từ $1$ đến $n$
$m$ dòng tiếp theo mô tả danh sách cạnh. Mỗi dòng chứa hai số nguyên $a$ và $b$ với ý nghĩa có một cạnh nối giữa hai đỉnh $a$ và $b$
Đồ thị đã cho là một đơn đồ thị. Tức là giữa hai đỉnh bất kỳ chỉ có tối đa một cạnh nối giữa chúng và tất cả các cạnh đều nối giữa hai đỉnh phân biệt

Constraints

$1 \leq n \leq 10^5$
$1 \leq m \leq 2 \cdot 10^5$
$1 \leq a, b \leq n$

Output

In ra $m$ dòng mô tả chiều của các cạnh. Mỗi dòng chứa hai số nguyên $a$ và $b$ với ý nghĩa có một cung nối từ đỉnh $a$ đến đỉnh $b$
Bạn có thể in ra phương án bất kỳ. Nếu không tồn tại đáp án, in ra IMPOSSIBLE

Example

Test 1

Input

Output

1 2
2 3
3 1

11. CSES - Dynamic Connectivity | Liên thông động

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

Cho một đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh. Có 2 loại thao tác:

Thêm một cạnh mới vào giữa hai đỉnh $a$ và $b$.
Xóa một cạnh tồn tại giữa hai đỉnh $a$ và $b$.

Tính số thành phần liên thông sau mỗi hành động.

Input

Dòng đầu tiên chứa ba số nguyên $N$, $M$ và $K$: số đỉnh, cạnh và thao tác.
$M$ dòng tiếp theo mô tả số đỉnh. Mỗi dòng gồm hai số nguyên $a$ và $b$: có một cạnh giữa hai đỉnh $a$ và $b$. Có ít nhất một cạnh giữa hai cặp đỉnh bất kì.
$K$ dòng tiếp theo mô tả số thao tác. Mỗi dòng gồm ba số nguyên $t$, $a$ và $b$: thêm $(t = 1)$ hoặc xóa $(t = 2)$ một cạnh giữa hai đỉnh $a$ và $b$. Cạnh chỉ được tạo khi chưa tồn tại cạnh nào giữa hai đỉnh và chỉ được xóa khi tồn tại một cạnh giữa hai đỉnh.

Constraints

$2 \leq N \leq 2\cdot 10^5$
$1 \leq M, K \leq 10^5$
$1 \leq a, b \leq n$

Output

In ra $k + 1$ số nguyên gồm: số thành phần liên thông trước khi thực hiện thao tác và số thành phần liên thông sau mỗi thao tác.

Example

Test 1

Input

Output

2 2 2 1

12. Bài toán đếm đường đi trong đồ thị đơn có hướng(*)

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

Cho một đồ thị đơn, có hướng $G$ với $N$ đỉnh, được đánh số $1,2,3,4,...,N$

Với mỗi $i,j(1\le i,j\le N)$, bạn được cho $1$ số nguyên $a_{i,j}$ thể hiện sự kết nối có hướng giữa hai đỉnh $i$ và $j$. Nếu $a_{i,j}=1$ thì đỉnh $i$ được nối với đỉnh $j$ theo chiều từ $i$ đến $j$, nếu $a_{i,j}=0$ thì không tồn tại kết nối giữa hai đỉnh $i,j$.

Yêu cầu: Tìm số đường khác nhau có độ dài là $K$ trong $G$, biết rằng mỗi con đường này có thể đi qua một cạnh nhiều lần.

Vì đáp số có thể lớn nên cần lấy mod $10^9+7$ trước khi in ra

Input

Dòng thứ nhất chứa hai số nguyên $N,K(1\le N\le 50,1\le K\le 10^{18})$
$N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $a_{i,1},a_{i,2},...,a_{i,n}(1\le i\le N, a_{i,j}\in \left\{0,1\right\})$

Output

In ra đáp án sau khi đã lấy mod $10^9+7$

Example

Test 1

Input

Output

Note

Những con đường có độ dài là $3$ là :

$1\rightarrow 2 \rightarrow 1 \rightarrow 2$
$2\rightarrow 1 \rightarrow 2 \rightarrow 1$
$2\rightarrow 1 \rightarrow 2 \rightarrow 3$