vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
There are n cities and n-1 two-way roads in Treeland. Each road connects a pair of different cities. From any city you can drive to any other, moving only along the roads. Cities are numbered from 1 to n. Yes, of course, you recognized an undirected tree in this description.

The government plans to repair all the roads. Each road will be repaired by some private company. In total, the country has 10^6 private companies that are numbered from 1 to 10^6. It is possible that some companies will not repair roads at all, and some will repair many roads.

To simplify the control over the work of private companies, the following restriction was introduced: for each city, we calculate the number of different companies that repair roads that have this city at one end. This number for each city should not exceed 2. In other words, for each city, there should be no more than two different companies that repair roads related to this city.

The National Anti-Corruption Committee of Treeland raises concerns that all (or almost all) of the work will go to one private company. For this reason, the committee requires that roads be distributed among companies in such a way as to minimize the value of r. For each company, we calculate the number of roads assigned to it, the maximum among all companies is called the number r.

Help the government find such a way to distribute all roads among companies in the required way.

Input

The first line contains an integer t (1 ≤ t ≤ 1000) — the number of input cases in the input. Next, the input cases themselves are given. The first line of each test case set contains an integer n (2 ≤ n ≤ 3000) — the number of cities in Treeland. Next, in the n-1 lines the roads are written: a line contains two integers x_i, y_i (1 ≤ x_i, y_i ≤ n), indicating that the i-th road connects the cities x_i and y_i.

It is guaranteed that the sum of all values n ​​for all test cases in the input does not exceed 3000.

Output

Print the answers for all t test cases in the input. Each test case must begin with a line that contains r — the minimum possible number of roads assigned to the most used company. Next, in the next line print n-1 the number c_1, c_2, ..., c_{n-1} (1 ≤ c_i ≤ 10^6), where c_i indicates the company to repair the i-th road. If there are several optimal assignments, print any of them.

Example

Input


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


Output


1
10 20
3
1 1 1 2 2 
2
11 11 12 13 12 13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
CSS colors are defined using a hexadecimal (HEX) notation for the combination of Red, Green, and Blue color values (RGB).

Specifications of HEX Color Code

■ It must start with a '#' symbol.

■ It can have $3$ or $\boldsymbol{6}$ digits.

■ Each digit is in the range of $\mbox{o}$ to $\mbox{F}$. ($1,2,3,4,5,6,7,8,9,0,A,B,C,D,E$ and $\mbox{F}$).

■ $A-F$ letters can be lower case. ($a,b,c,d,e$ and $\mbox{f}$ are also valid digits).

Examples  

Valid Hex Color Codes
#FFF 
#025 
#F0A1FB 

Invalid Hex Color Codes
#fffabg
#abcf
#12365erff

You are given $N$ lines of CSS code. Your task is to print all valid Hex Color Codes, in order of their occurrence from top to bottom. 

CSS Code Pattern

Selector
{
	Property: Value;
}

Input Format

The first line contains $N$, the number of code lines.

The next $N$ lines contains CSS Codes.  

Constraints

$0<N<50$

Output Format

Output the color codes with '#' symbols on separate lines.

Sample Input
11
#BED
{
    color: #FfFdF8; background-color:#aef;
    font-size: 123px;
    background: -webkit-linear-gradient(top, #f9f9f9, #fff);
}
#Cab
{
    background-color: #ABC;
    border: 2px dashed #fff;
}   

Sample Output
#FfFdF8
#aef
#f9f9f9
#fff
#ABC
#fff

Explanation

#BED and #Cab satisfy the Hex Color Code criteria, but they are used as selectors and not as color codes in the given CSS. 

Hence, the valid color codes are:

#FfFdF8

#aef

#f9f9f9

#fff

#ABC

#fff

Note: There are no comments ( // or /* */)  in CSS Code.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice has a birthday today, so she invited home her best friend Bob. Now Bob needs to find a way to commute to the Alice's home.

In the city in which Alice and Bob live, the first metro line is being built. This metro line contains $n$ stations numbered from $1$ to $n$. Bob lives near the station with number $1$, while Alice lives near the station with number $s$. The metro line has two tracks. Trains on the first track go from the station $1$ to the station $n$ and trains on the second track go in reverse direction. Just after the train arrives to the end of its track, it goes to the depot immediately, so it is impossible to travel on it after that.

Some stations are not yet open at all and some are only partially open — for each station and for each track it is known whether the station is closed for that track or not. If a station is closed for some track, all trains going in this track's direction pass the station without stopping on it.

When the Bob got the information on opened and closed stations, he found that traveling by metro may be unexpectedly complicated. Help Bob determine whether he can travel to the Alice's home by metro or he should search for some other transport.


-----Input-----

The first line contains two integers $n$ and $s$ ($2 \le s \le n \le 1000$) — the number of stations in the metro and the number of the station where Alice's home is located. Bob lives at station $1$.

Next lines describe information about closed and open stations.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i = 0$ or $a_i = 1$). If $a_i = 1$, then the $i$-th station is open on the first track (that is, in the direction of increasing station numbers). Otherwise the station is closed on the first track.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($b_i = 0$ or $b_i = 1$). If $b_i = 1$, then the $i$-th station is open on the second track (that is, in the direction of decreasing station numbers). Otherwise the station is closed on the second track.


-----Output-----

Print "YES" (quotes for clarity) if Bob will be able to commute to the Alice's home by metro and "NO" (quotes for clarity) otherwise.

You can print each letter in any case (upper or lower).


-----Examples-----
Input
5 3
1 1 1 1 1
1 1 1 1 1

Output
YES

Input
5 4
1 0 0 0 1
0 1 1 1 1

Output
YES

Input
5 2
0 1 1 1 1
1 1 1 1 1

Output
NO



-----Note-----

In the first example, all stations are opened, so Bob can simply travel to the station with number $3$.

In the second example, Bob should travel to the station $5$ first, switch to the second track and travel to the station $4$ then.

In the third example, Bob simply can't enter the train going in the direction of Alice's home.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Cartesian coordinate system is set in the sky. There you can see n stars, the i-th has coordinates (x_{i}, y_{i}), a maximum brightness c, equal for all stars, and an initial brightness s_{i} (0 ≤ s_{i} ≤ c).

Over time the stars twinkle. At moment 0 the i-th star has brightness s_{i}. Let at moment t some star has brightness x. Then at moment (t + 1) this star will have brightness x + 1, if x + 1 ≤ c, and 0, otherwise.

You want to look at the sky q times. In the i-th time you will look at the moment t_{i} and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates (x_1i, y_1i) and the upper right — (x_2i, y_2i). For each view, you want to know the total brightness of the stars lying in the viewed rectangle.

A star lies in a rectangle if it lies on its border or lies strictly inside it.


-----Input-----

The first line contains three integers n, q, c (1 ≤ n, q ≤ 10^5, 1 ≤ c ≤ 10) — the number of the stars, the number of the views and the maximum brightness of the stars.

The next n lines contain the stars description. The i-th from these lines contains three integers x_{i}, y_{i}, s_{i} (1 ≤ x_{i}, y_{i} ≤ 100, 0 ≤ s_{i} ≤ c ≤ 10) — the coordinates of i-th star and its initial brightness.

The next q lines contain the views description. The i-th from these lines contains five integers t_{i}, x_1i, y_1i, x_2i, y_2i (0 ≤ t_{i} ≤ 10^9, 1 ≤ x_1i < x_2i ≤ 100, 1 ≤ y_1i < y_2i ≤ 100) — the moment of the i-th view and the coordinates of the viewed rectangle.


-----Output-----

For each view print the total brightness of the viewed stars.


-----Examples-----
Input
2 3 3
1 1 1
3 2 0
2 1 1 2 2
0 2 1 4 5
5 1 1 5 5

Output
3
0
3

Input
3 4 5
1 1 2
2 3 0
3 3 1
0 1 1 100 100
1 2 2 4 4
2 2 1 4 7
1 50 50 51 51

Output
3
3
5
0



-----Note-----

Let's consider the first example.

At the first view, you can see only the first star. At moment 2 its brightness is 3, so the answer is 3.

At the second view, you can see only the second star. At moment 0 its brightness is 0, so the answer is 0.

At the third view, you can see both stars. At moment 5 brightness of the first is 2, and brightness of the second is 1, so the answer is 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Squareland national forest is divided into equal 1 × 1 square plots aligned with north-south and east-west directions. Each plot can be uniquely described by integer Cartesian coordinates (x, y) of its south-west corner.

Three friends, Alice, Bob, and Charlie are going to buy three distinct plots of land A, B, C in the forest. Initially, all plots in the forest (including the plots A, B, C) are covered by trees. The friends want to visit each other, so they want to clean some of the plots from trees. After cleaning, one should be able to reach any of the plots A, B, C from any other one of those by moving through adjacent cleared plots. Two plots are adjacent if they share a side.

<image> For example, A=(0,0), B=(1,1), C=(2,2). The minimal number of plots to be cleared is 5. One of the ways to do it is shown with the gray color.

Of course, the friends don't want to strain too much. Help them find out the smallest number of plots they need to clean from trees.

Input

The first line contains two integers x_A and y_A — coordinates of the plot A (0 ≤ x_A, y_A ≤ 1000). The following two lines describe coordinates (x_B, y_B) and (x_C, y_C) of plots B and C respectively in the same format (0 ≤ x_B, y_B, x_C, y_C ≤ 1000). It is guaranteed that all three plots are distinct.

Output

On the first line print a single integer k — the smallest number of plots needed to be cleaned from trees. The following k lines should contain coordinates of all plots needed to be cleaned. All k plots should be distinct. You can output the plots in any order.

If there are multiple solutions, print any of them.

Examples

Input


0 0
1 1
2 2


Output


5
0 0
1 0
1 1
1 2
2 2


Input


0 0
2 0
1 1


Output


4
0 0
1 0
1 1
2 0

Note

The first example is shown on the picture in the legend.

The second example is illustrated with the following image:

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Greed

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Jafar has *n* cans of cola. Each can is described by two integers: remaining volume of cola *a**i* and can's capacity *b**i* (*a**i* <=≤<= *b**i*).

Jafar has decided to pour all remaining cola into just 2 cans, determine if he can do this or not!

Input Specification:
The first line of the input contains one integer *n* (2<=≤<=*n*<=≤<=100<=000) — number of cola cans.

The second line contains *n* space-separated integers *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=109) — volume of remaining cola in cans.

The third line contains *n* space-separated integers that *b*1,<=*b*2,<=...,<=*b**n* (*a**i*<=≤<=*b**i*<=≤<=109) — capacities of the cans.

Output Specification:
Print "YES" (without quotes) if it is possible to pour all remaining cola in 2 cans. Otherwise print "NO" (without quotes).

You can print each letter in any case (upper or lower).

Demo Input:
['2\n3 5\n3 6\n', '3\n6 8 9\n6 10 12\n', '5\n0 0 5 0 0\n1 1 8 10 5\n', '4\n4 1 0 3\n5 2 2 3\n']

Demo Output:
['YES\n', 'NO\n', 'YES\n', 'YES\n']

Note:
In the first sample, there are already 2 cans, so the answer is "YES".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a two player card game, you have $n$ minions on the board and the opponent has $m$ minions. Each minion has a health between $1$ and $6$. 

You are contemplating your next move. You want to play an “Explosion” spell which deals $d$ units of damage randomly distributed across all minions. The damage is dealt one unit at a time to some remaining minion on the board. Each living minion (including your own) has the same chance of receiving each unit of damage. When a minion receives a unit of damage, its health is decreased by one. As soon as the health of a minion reaches zero, it is immediately removed from the board, before the next damage is dealt. If there are no minions left on the board, any excess damage caused by the spell is ignored.

Given the current health of all minions, what is the probability that the Explosion will remove all of the opponent’s minions? Note that it does not matter if all your own minions die in the process as well, and the damage continues to be dealt even if all your own minions are gone.

-----Input-----
The first line of input contains the three integers $n$, $m$, and $d$ ($1 \le n, m \le 5$, $1 \le d \le 100$). Then follows a line containing $n$ integers, the current health of all your minions. Finally, the third line contains $m$ integers, the current health of all the opponent’s minions. All healths are between $1$ and $6$ (inclusive).

-----Output-----
Output the probability that the Explosion removes all the opponent’s minions, accurate up to an absolute error of $10^{-6}$.

-----Examples-----
Sample Input:
1 2 2
2
1 1
Sample Output:
0.3333333333

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After finding and moving to the new planet that supports human life, discussions started on which currency should be used. After long negotiations, Bitcoin was ultimately chosen as the universal currency.

These were the great news for Alice, whose grandfather got into Bitcoin mining in 2013, and accumulated a lot of them throughout the years. Unfortunately, when paying something in bitcoin everyone can see how many bitcoins you have in your public address wallet. 

This worried Alice, so she decided to split her bitcoins among multiple different addresses, so that every address has at most $x$ satoshi (1 bitcoin = $10^8$ satoshi). She can create new public address wallets for free and is willing to pay $f$ fee in satoshi per transaction to ensure acceptable speed of transfer. The fee is deducted from the address the transaction was sent from. Tell Alice how much total fee in satoshi she will need to pay to achieve her goal.


-----Input-----

First line contains number $N$ ($1 \leq N \leq 200\,000$) representing total number of public addresses Alice has.

Next line contains $N$ integer numbers $a_i$ ($1 \leq a_i \leq 10^9$) separated by a single space, representing how many satoshi Alice has in her public addresses.

Last line contains two numbers $x$, $f$ ($1 \leq f < x \leq 10^9$) representing maximum number of satoshies Alice can have in one address, as well as fee in satoshies she is willing to pay per transaction. 


-----Output-----

Output one integer number representing total fee in satoshi Alice will need to pay to achieve her goal.


-----Example-----
Input
3
13 7 6
6 2

Output
4



-----Note-----

Alice can make two transactions in a following way:

0. 13 7 6 (initial state)

1. 6 7 6 5 (create new address and transfer from first public address 5 satoshies)

2. 6 4 6 5 1 (create new address and transfer from second address 1 satoshi)

Since cost per transaction is 2 satoshies, total fee is 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
John has just bought a new car and is planning a journey around the country. Country has N cities, some of which are connected by bidirectional roads. There are N - 1 roads and every city is reachable from any other city. Cities are labeled from 1 to N.

John first has to select from which city he will start his journey. After that, he spends one day in a city and then travels to a randomly choosen city which is directly connected to his current one and which he has not yet visited. He does this until he can't continue obeying these rules.

To select the starting city, he calls his friend Jack for advice. Jack is also starting a big casino business and wants to open casinos in some of the cities (max 1 per city, maybe nowhere). Jack knows John well and he knows that if he visits a city with a casino, he will gamble exactly once before continuing his journey.

He also knows that if John enters a casino in a good mood, he will leave it in a bad mood and vice versa. Since he is John's friend, he wants him to be in a good mood at the moment when he finishes his journey. John is in a good mood before starting the journey.

In how many ways can Jack select a starting city for John and cities where he will build casinos such that no matter how John travels, he will be in a good mood at the end? Print answer modulo 10^9 + 7.


-----Input-----

In the first line, a positive integer N (1 ≤ N ≤ 100000), the number of cities. 

In the next N - 1 lines, two numbers a,  b (1 ≤ a, b ≤ N) separated by a single space meaning that cities a and b are connected by a bidirectional road.


-----Output-----

Output one number, the answer to the problem modulo 10^9 + 7.


-----Examples-----
Input
2
1 2

Output
4

Input
3
1 2
2 3

Output
10



-----Note-----

Example 1: If Jack selects city 1 as John's starting city, he can either build 0 casinos, so John will be happy all the time, or build a casino in both cities, so John would visit a casino in city 1, become unhappy, then go to city 2, visit a casino there and become happy and his journey ends there because he can't go back to city 1. If Jack selects city 2 for start, everything is symmetrical, so the answer is 4.

Example 2: If Jack tells John to start from city 1, he can either build casinos in 0 or 2 cities (total 4 possibilities). If he tells him to start from city 2, then John's journey will either contain cities 2 and 1 or 2 and 3. Therefore, Jack will either have to build no casinos, or build them in all three cities. With other options, he risks John ending his journey unhappy. Starting from 3 is symmetric to starting from 1, so in total we have 4 + 2 + 4 = 10 options.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Python has built-in string validation methods for basic data. It can check if a string is composed of alphabetical characters, alphanumeric characters, digits, etc.

str.isalnum() 

This method checks if all the characters of a string are alphanumeric (a-z, A-Z and 0-9).

>>> print 'ab123'.isalnum()
True
>>> print 'ab123#'.isalnum()
False

str.isalpha() 

This method checks if all the characters of a string are alphabetical (a-z and A-Z).

>>> print 'abcD'.isalpha()
True
>>> print 'abcd1'.isalpha()
False

str.isdigit() 

This method checks if all the characters of a string are digits (0-9).

>>> print '1234'.isdigit()
True
>>> print '123edsd'.isdigit()
False

str.islower() 

This method checks if all the characters of a string are lowercase characters (a-z).

>>> print 'abcd123#'.islower()
True
>>> print 'Abcd123#'.islower()
False

str.isupper() 

This method checks if all the characters of a string are uppercase characters (A-Z).

>>> print 'ABCD123#'.isupper()
True
>>> print 'Abcd123#'.isupper()
False

Task

You are given a string $\mbox{S}$. 

Your task is to find out if the string $\mbox{S}$ contains: alphanumeric characters, alphabetical characters, digits, lowercase and uppercase characters. 

Input Format

A single line containing a string $\mbox{S}$.

Constraints

$0<len(S)<1000$

Output Format

In the first line, print True if $\mbox{S}$ has any alphanumeric characters. Otherwise, print False. 

In the second line, print True if $\mbox{S}$ has any alphabetical characters. Otherwise, print False. 

In the third line, print True if $\mbox{S}$ has any digits. Otherwise, print False. 

In the fourth line, print True if $\mbox{S}$ has any lowercase characters. Otherwise, print False. 

In the fifth line, print True if $\mbox{S}$ has any uppercase characters. Otherwise, print False.  

Sample Input
qA2

Sample Output
True
True
True
True
True

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Long ago during the Jurassic Park age, there was a company TopHunters, which used to conduct hunting competitions for the Dinosaurs around the world. Petrosaurus was believed to be the greatest hunter of that time and all other dinosaurs enjoyed watching the hunting videos posted by him in the forums ( yes, they had a website :) ). 
Many Indian dinosaurs used to post in sms language in the forums and annoy others. Vexosaurus was so annoyed reading the posts with numbers used in place of letters. He decided to correct all those posts, before the forums get Rusty. Could you please code for him and replace the following words in 1st column with their corresponding words in 2nd column




8ate
w8wait
gr8great
4for
b4before


     







Lets not make this complex and just replace the words when they appear entirely as a word themselves, and not as a subpart of bigger words ( see examples for clarity ). A word is a continuous sequence of non-space characters.
Disclaimer : This is just a fictional story. Any resemblance to real persons or company or dinosaurs is purely coincidental ;)


Input
First line contains T [ number of test cases, around 50 ]. Each of the next T lines contains a sentence with not more than 100 characters [ 'a' - 'z' , '0' - '9' , space ]. There can be 2 or more continuous spaces and you have to preserve them, in the output. Input sentence will not begin or end with a space.


Output
For each test case, output the corrected sentence, in a new line. 


Example

Input:
3
i 8 food b4
gr8 2 see you w8ing
1234   5678   9

Output:
i ate food before
great 2 see you w8ing
1234   5678   9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an unweighted tree with n vertices. Recall that a tree is a connected undirected graph without cycles.

Your task is to choose three distinct vertices a, b, c on this tree such that the number of edges which belong to at least one of the simple paths between a and b, b and c, or a and c is the maximum possible. See the notes section for a better understanding.

The simple path is the path that visits each vertex at most once.

Input

The first line contains one integer number n (3 ≤ n ≤ 2 ⋅ 10^5) — the number of vertices in the tree. 

Next n - 1 lines describe the edges of the tree in form a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i). It is guaranteed that given graph is a tree.

Output

In the first line print one integer res — the maximum number of edges which belong to at least one of the simple paths between a and b, b and c, or a and c.

In the second line print three integers a, b, c such that 1 ≤ a, b, c ≤ n and a ≠, b ≠ c, a ≠ c.

If there are several answers, you can print any.

Example

Input


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


Output


5
1 8 6

Note

The picture corresponding to the first example (and another one correct answer):

<image>

If you choose vertices 1, 5, 6 then the path between 1 and 5 consists of edges (1, 2), (2, 3), (3, 4), (4, 5), the path between 1 and 6 consists of edges (1, 2), (2, 3), (3, 4), (4, 6) and the path between 5 and 6 consists of edges (4, 5), (4, 6). The union of these paths is (1, 2), (2, 3), (3, 4), (4, 5), (4, 6) so the answer is 5. It can be shown that there is no better answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.