Problem Background

Day 1 Problem D.

This problem is translated from EGOI2023 bikesvscars.

Problem Description

In Lund, cycling is a common mode of transportation, but sometimes narrow streets cannot accommodate both bikes and cars. To improve this situation, the local government wants to completely redesign the local street network.

Lund has $N$ key locations (numbered from $0$ to $N-1$), between which people often travel. People travel between two locations via a path, which is a series of streets from one location to another. A mode of transportation (car or bike) can travel on a path if and only if all the streets it traverses are at least as wide as it. Each newly constructed street connects two key locations and has a width $W$. This width can be arbitrarily divided into bike lanes and car lanes. In Lund, some engineers recently invented cars and bikes with a width of $0$ (they can travel on roads with a width of $0$).

These engineers have measured the widths of cars and bikes in the city. For every pair of key locations, they know the width of the widest car and the widest bike that can travel between them, but the government also requires that wider cars and bikes cannot travel between them.

Formally, for any $i, j$ ($0 \le i < j \le N-1$), you know two integers $C_{i,j}$ and $B_{i,j}$. Your task is to construct a street network connecting these $N$ locations. The width of each street is $W$, but for any street $s$, you can choose its bike lane width $b_s$ and car lane width $W-b_s$. This network must meet the following requirements:

• It must be possible to travel between any two locations. This may require a bike or car with a width of $0$.
• For every pair of locations $i, j$ (where $i < j$), it must be possible to travel between $i$ and $j$ using only car lanes with a width of at least $C_{i,j}$. Additionally, $C_{i,j}$ is the largest number with this property. This means that for all paths between $i$ and $j$, at least one street must have a car lane width not exceeding $C_{i,j}$.
• For every pair of locations $i, j$ (where $i < j$), it must be possible to travel between $i$ and $j$ using only bike lanes with a width of at least $B_{i,j}$. Additionally, $B_{i,j}$ is the largest number with this property.

Can you help the Lund government design such a street network? Due to budget constraints, you can build at most $2023$ streets. You can build multiple streets between the same pair of key locations, but you cannot build a street connecting a location to itself. All streets are bidirectional.

Input Format

The first line contains two integers $N, W$, representing the number of key locations and the street width.

The next $N-1$ lines contain $C_{i,j}$. The $j$-th line contains all $C_{i,j}$ where $i < j$. Therefore, the first line will only contain $C_{0,1}$, the second line contains $C_{0,2}$ and $C_{1,2}$, the third line contains $C_{0,3}, C_{1,3}, C_{2,3}$, and so on.

The next $N-1$ lines contain $B_{i,j}$, in the same format as $C_{i,j}$.

Output Format

If no street network meeting the requirements exists, output NO.

Otherwise, the first line contains an integer $M$, representing the number of streets you build.

The next $M$ lines contain three integers each, $u, v, b$, representing a street with a bike lane width of $b$ (and a car lane width of $W-b$) connecting $u$ and $v$.

You can use at most $2023$ streets. Your output must ensure $0 \le b \le W$, $0 \le u, v \le N-1$, and $u \ne v$. You can use multiple streets between the same pair of key locations (with different bike lane widths).

If there are multiple solutions, you can output any one.

Sample Input and Output

Sample Input #1

2 1
1
1

Sample Output #1

2
0 1 0
0 1 1

Sample Input #2

4 1
0
0 1
0 0 1
1
1 1
1 1 1

Sample Output #2

NO

Sample Input #3

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

Sample Output #3

8
0 1 1
0 2 3
1 2 2
0 3 6
2 4 5
3 4 3
3 5 1
4 5 4

Notes/Hints

Sample 1 Explanation

In Sample 1, the street width is $1$, and we need one bike lane with a width of at least $1$ and one car lane with a width of at least $1$ to connect $0$ and $1$. The solution is to use two separate streets, one with a bike lane width of $1$ and the other with a car lane width of $1$.

Sample 2 Explanation

In Sample 2, the street width is still $1$, and we need a bike lane with a width of $1$ to connect any two key locations, and a car lane with a width of $1$ to connect $1, 2$ and $2, 3$. This conflicts with $C_{1,3}=0$, which means there should not be a car lane with a width of $1$ from $1$ to $3$, and we can merge two previously mentioned paths to form such a path. Therefore, it is impossible to construct a street network meeting the requirements.

Sample 3 Explanation

In Sample 3, the street network in the figure meets all the requirements. For example, there should be a car lane with a width of $1=C_{0,5}$ between $0$ and $5$ (path $0 \to 2 \to 4 \to 5$), and a bike lane with a width of $3=B_{0,5}$ between $0$ and $5$ (path $0 \to 3 \to 4 \to 5$). It can also be verified that there is no path with a larger width limit. Note that Sample 3 may have many other solutions.

Data Range

For all data, $2 \le N \le 500$, $1 \le W \le 10^6$, $0 \le C_{i,j}, B_{i,j} \le W$.

• Subtask 1 (10 points): All $C_{i,j}$ are the same, all $B_{i,j}$ are the same, $N \le 40$.
• Subtask 2 (5 points): All $C_{i,j}$ are the same, all $B_{i,j}$ are the same.
• Subtask 3 (17 points): $N \le 40$.
• Subtask 4 (18 points): $W=1$.
• Subtask 5 (19 points): All $B_{i,j}$ are the same.
• Subtask 6 (31 points): No special restrictions.

见题面 Input 部分

见题面 Output 部分