Problem Description

Once upon a time, there were two people named Lu Renjia and Lu Renyi, and they went to take the subway.

Lu Renjia wanted to travel from Xunlimen to Guangbutun, while Lu Renyi wanted to travel from Guangbutun to Xunlimen.

As hardcore subway fans, Lu Renjia and Lu Renyi know the fare rules of the Wuhan Metro very well.

Wuhan Metro Line $2$ is a straight line with a total of $m$ stations, numbered in order as $1,\cdots,m$.

To take the subway, you need to tap a transit card called Wuhan Tong. You tap once when entering and once when exiting. When exiting, the system deducts a fare from the Wuhan Tong based on the distance between the start station and the destination station. That is, if $cost(i, j)$ denotes the cost of entering at station $i$ and exiting at station $j$, then:

The clever Lu Renjia and Lu Renyi discovered that the start station of a trip is recorded on the Wuhan Tong when you tap in. Also, the fare does not depend on travel time: you can enter at station $i$, play on the train all day, and exit at station $j$, and you still pay $cost(i,j)$.

So Lu Renjia and Lu Renyi had an idea and came up with a brilliant plan to ride for free.

First, Lu Renjia enters at Xunlimen and departs, then gets off and waits at the intermediate station Pangxiejia. At the same time, Lu Renyi enters at Guangbutun and departs, and also gets off and waits at Pangxiejia.

Then Lu Renjia and Lu Renyi meet at Pangxiejia and swap their Wuhan Tong cards.

Finally, Lu Renjia takes the subway to Guangbutun. At this time, the start station recorded on Lu Renjia's Wuhan Tong is Guangbutun, so the fare deducted is $0$.

Lu Renyi takes the subway to Xunlimen. At this time, the start station recorded on Lu Renyi's Wuhan Tong is Xunlimen, so the fare deducted is also $0$.

In this way, they complete one free ride.

Now Lu Renjia and Lu Renyi start thinking: suppose there are $n$ people taking the subway, numbered $1,\cdots,n$. Person $i$ travels from station $s_i$ to station $e_i$ with $s_i\ne e_i$, taking the subway along a shortest path. That is:

• If $s_i<e_i$, they pass through $s_i,s_i+1,\cdots,e_i-1,e_i$ in order.
• If $s_i>e_i$, they pass through $s_i,s_i-1,\cdots,e_i+1,e_i$ in order.

Assuming they are smart enough to get off midway and swap tickets, what is the minimum total cost for their trips?

The ride procedure is defined as follows:

• At the beginning, everyone taps in. Person $i$ is at station $s_i$.
• Each time, you may perform one of the following two operations:
• $0\;x\;y$: Let person $x$ take the subway to station $y$ and get off. Detours are not allowed, meaning they must ride in the direction closer to $e_x$. Also, traveling from the current station to the same station is not allowed, so $y$ cannot be the station number where person $x$ is currently located. You must ensure $1\le x\le n,1\le y\le m$.
• $1\;x\;y$: Let person $x$ and person $y$ swap their Wuhan Tong cards. Note that only two people who are currently at the same station can swap tickets. You must ensure $1\le x\le n,1\le y\le n$.
• During each operation, anyone not mentioned in the operation stays where they are.
• After all operations, everyone taps out together. Note that you must ensure that person $\boldsymbol i$ is at station $\boldsymbol{e_i}$ at this time.
• Finally, after everyone exits, the sum of all fares deducted from the Wuhan Tong cards must be minimized. Find a minimum-cost ride plan.

Of course, Lu Renjia and Lu Renyi know how to do it. But they want to test you.

Input Format

The first line contains a positive integer $T$, the number of test cases. Then follow $T$ test cases. For each test case:

The first line contains two positive integers $n,m$ separated by spaces, meaning there are $n$ people and $m$ subway stations.

The next $n$ lines each contain two positive integers $s_i,e_i$ separated by spaces, representing the start station and end station of person $i$. ($s_i\ne e_i,1\le s_i,e_i\le m$)

Output Format

For each test case, output an optimal plan. If multiple plans can achieve the minimum total deducted fare, output any one of them.

The first line contains two non-negative integers $ans,s$ separated by spaces, representing the minimum total cost and the number of operations. The number of operations must not be too large, and must satisfy $s\le400000$.

The next $s$ lines each contain three positive integers $type\;x\;y$ describing an operation. ($type\in\{0,1\}$, and the constraints on $x,y$ are as stated above)

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

7 5
0 1 5
1 3 1
0 1 7
0 2 6
0 3 1
0 3
0 1 7
1 2 1
0 2 1

Hint

For all test cases, $T\le6$.

(This problem is purely an idea by VFleaKing... Tests show that entering and then exiting costs $1.8$ yuan, so please do not try to imitate the behavior described in the statement...)

Translated by ChatGPT 5