Background

Day 1 Problem D.

Translated from EGOI2023 bikesvscars.

Problem Description

In Lund, cycling is a common way to get around, but sometimes narrow streets make it hard for cars and bicycles to pass. To improve this situation, the local government wants to completely redesign the city’s street network.

There are $N$ key locations in Lund (numbered from $0$ to $N-1$), and people often travel between them. People travel between two locations along a path, where a path is a sequence of streets from one location to the other. A vehicle (car or bicycle) can travel along a path if and only if all streets on the path are at least as wide as the vehicle. Each newly built street connects two key locations and has total width $W$. This width can be split in any way into a bicycle lane and a car lane. In Lund, some engineers have recently invented cars and bicycles of width $0$ (they can travel on roads of width $0$).

These engineers measured the widths of cars and bicycles in the city. For every pair of key locations, they know the width of the widest car and the widest bicycle that can travel between them, and the government also requires that wider cars and bicycles must not be able to travel between them.

Formally, for any $i,j$ ($0\le i < j\le N-1$), you are given two integers $C_{i,j}$ and $B_{i,j}$. Your task is to construct a street network connecting these $N$ locations. All streets have total width $W$, but for any street $s$, you may choose its bicycle-lane width $b_s$ and car-lane width $W-b_s$. The network must satisfy:

• It must be possible to travel between any two locations. This may require a bicycle or car of width $0$.
• For each pair of locations $i,j$ (where $i<j$), it must be possible to travel between $i$ and $j$ using only car lanes of width at least $C_{i,j}$. Also, $C_{i,j}$ is the largest number with this property. This means that for every path between $i$ and $j$, there must be at least one street whose car-lane width is at most $C_{i,j}$.
• For each pair of locations $i,j$ (where $i<j$), it must be possible to travel between $i$ and $j$ using only bicycle lanes of width at least $B_{i,j}$. Also, $B_{i,j}$ is the largest number with this property.

Can you help the Lund government design such a street network? Because the budget is limited, you may build at most $2023$ streets. You may build multiple streets between the same pair of key locations, but you may not build a street from a location to itself. All streets are bidirectional.

Input Format

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

The next $N-1$ lines contain $C_{i,j}$. The $j$-th of these lines contains all $C_{i,j}$ with $i<j$. Therefore, the first line contains only $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 satisfying the requirements exists, output NO.

Otherwise, output an integer $M$ on the first line, the number of streets you build.

Then output $M$ lines, each containing three integers $u,v,b$, describing a street between $u$ and $v$ whose bicycle-lane width is $b$ (and car-lane width is $W-b$).

You may use at most $2023$ streets. The streets you output must satisfy $0\le b\le W$, $0\le u,v\le N-1$, and $u\ne v$. You may use multiple streets between the same pair of key locations (possibly with different bicycle-lane widths).

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

2 1
1
1

2
0 1 0
0 1 1

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

NO

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

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

Hint

Explanation of Sample 1

In sample $1$, the street width is $1$. We need a bicycle lane of width at least $1$ and a car lane of width at least $1$ between $0$ and $1$. The solution is to connect them with two separate streets: one with bicycle-lane width $1$, and the other with car-lane width $1$.

Explanation of Sample 2

In sample $2$, the street width is still $1$. We need a bicycle lane of width $1$ connecting every pair of key locations, and a car lane of width $1$ connecting $1,2$ and $2,3$. This contradicts $C_{1,3}=0$: there should not be a car-lane path of width $1$ from $1$ to $3$, but we could combine the two paths mentioned above to form such a path. Therefore, it is impossible to construct a street network that satisfies the requirements.

Explanation of Sample 3

In sample $3$, the street network in the figure satisfies all requirements. For example, there should be a car-lane path of width $1=C_{0,5}$ between $0$ and $5$ (path $0\to 2\to 4\to 5$), and a bicycle-lane path of width $3=B_{0,5}$ between $0$ and $5$ (path $0\to 3\to 4\to 5$). Also, one can verify that there is no path with a larger minimum width. Note that sample $3$ may have many other valid solutions.

Constraints

For all testdata, $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 equal, all $B_{i,j}$ are equal, $N\le 40$.
• Subtask 2 ($5$ points): all $C_{i,j}$ are equal, all $B_{i,j}$ are equal.
• Subtask 3 ($17$ points): $N\le 40$.
• Subtask 4 ($18$ points): $W=1$.
• Subtask 5 ($19$ points): all $B_{i,j}$ are equal.
• Subtask 6 ($31$ points): no special constraints.

Translated by ChatGPT 5