title: [USACO10OPEN] Water Slides G

description:
Inspired by the new water park at Machu Picchu in Peru, Farmer John has decided to build one for the cows. Its biggest

attraction is to be a giant water slide of a peculiar design. The superslide comprises E (1 <= E <=

150,000) mini slides connecting V (2 <= V <= 50,000) small pools conveniently labeled 1..V. Every mini slide must be traversed in its proper direction and may not be traversed backwards. The cows start at pool number 1 and traverse successive mini slides until they end up in the pool number V, the final pool. Every pool (except 1, the first one) includes at least one mini slide entering it and (except V, the last one) at least one (different) mini slide exiting it.

Furthermore, a cow can reach the end of the ride (pool V) from any pool by going down a sequence of mini slides. Finally, since this is a slide, it is not possible to leave a pool and then encounter that pool again after traversing some set of mini slides.

Each mini slide i runs from pool P\_i to pool Q\_i (1 <= P\_i <= V; 1 <= Q\_i <= V; P\_i != Q\_i) and has an associated fun value F\_i (0 <= F\_i <= 2,000,000,000). Bessie's total fun for any given trip down the superslide is the sum of the fun values of all the mini slides traversed.

Bessie naturally wants to have as much fun as possible, given the long time that she spends in the slide's queue waiting for the ride. Generally, she carefully chooses which mini slide to follow out of each pool. She is a cow, however, and no more than K (1 <= K <= 10) times as she splashes down the slide, she loses control and follows a random mini slide out of a pool (this can even happen on pool 1).

If Bessie chooses so as to maximize her fun in the worst case, how much fun is she guaranteed to have for a given super-slide?

By way of example, consider a small park that has 3 pools (pool id's shown in brackets) and four mini slides; K has the value 1 (fun values shown outside of brackets):

[1]
/   \
5 -> /     \ <- 9

/       \

[2]---3---[3]

\_\_5\_\_/

She alway starts at pool 1 and ends and pool 3. If she had her way, she'd ride direct from pool 1 to pool 2 and then on the higher-fun mini slide (with fun value 5) to slide 3 for a total fun value of 5+5=10. But, if she loses control at pool 1, she might slide directly from pool 1 to pool 3 for total fun 9. If she loses control at pool 2, she could reduce her total fun to just 5+3 = 8.

Bessie wants to find the most fun she can have so she strives to choose 1->3 for a total fun of 9. If she loses control at pool 1 and ends up on mini slide 1->2, she knows she will not lose control at pool 2 and will end up with fun 10. Thus, she knows her minimum fun will always be at least 9.

inputFormat:
\* Line 1: Three space separated integers: V, E, and K

\* Lines 2..E + 1: Line i+1 contains three space separated integers: P\_i, Q\_i, and F\_i

outputFormat: \* Line 1: A single line with a single integer that is the minimum fun that Bessie can guarantee she can have.

translation:
给定 $V$ 个节点、$E$ 条边的带权 DAG（保证只有 $1$ 号节点入度为 $0$，$V$ 号节点出度为 $0$），要求找一条 $1$ 到 $V$ 的路径，保证恰有 $k$ 次在某个节点时下一步的移动的决策为最小化路径边权和（其余节点的决策为最大化）。求最大的可能的边权和。
$1\le V\le 5\times10^4,1\le E\le 1.5\times10^5,1\le k\le 10$，边权为不超过 $2\times 10^9$ 的非负整数。


title: [USACO10OPEN] Triangle Counting G

type: P

description:
Bessie is standing guard duty after

the big bad wolf was spotted stalking

```cpp
cows over at Farmer Don's spread.
Looking down from her guard tower in
utter boredom, she's decided to
perform intellectual exercises in
```
order to keep awake.
After imagining the field as an X,Y

grid, she recorded the coordinates of

the N (1 <= N <= 100,000)

conveniently numbered 1..N cows as

```cpp
X_i,Y_i (-100,000 <= X_i <= 100,000;
-100,000 <= Y_i <= 100,000; 1 <= i <=
N). She then mentally formed all possible triangles that could be made from subsets of the entire set of cow coordinates. She counts a triangle as 'golden' if it wholly contains the origin (0,0). The origin does not fall on the line between any pair of cows. Additionally, no cow is standing exactly on the origin.
Given the list of cow locations, calculate the number of 'golden' triangles that contain the origin so Bessie will know if she's doing a good job.
```
By way of example, consider 5 cows at these locations:
-5,0   0,2   11,2   -11,-6   11,-5

Below is a schematic layout of the field from Betsy's point of view:

```cpp
............|............
............*..........*.
............|............
-------*----+------------
............|............
............|............
............|............
............|............
............|..........*.
.*..........|............
............|............
```
All ten triangles below can be formed from the five points above:

By inspection, 5 of them contain the origin and hence are 'golden'.

在一只大灰狼偷偷潜入Farmer Don的牛群被群牛发现后，贝西现在不得不履行着她站岗的职责。从她的守卫塔向下瞭望简直就是一件烦透了的事情。她决定做一些开发智力的小练习，防止她睡着了。

想象牧场是一个X，Y平面的网格。她将N只奶牛标记为1…N (1 <= N <= 100,000)，每只奶牛的坐标为X\_i,Y\_i (-100,000 <= X\_i <= 100,000;-100,000 <= Y\_i <= 100,000; 1 <= i <=N)。然后她脑海里想象着所有可能由奶牛构成的三角形。如果一个三角形完全包含了原点(0,0)，那么她称这个三角形为“黄金三角形”。原点不会落在任何一对奶牛的连线上。另外，不会有奶牛在原点。

给出奶牛的坐标，计算出有多少个“黄金三角形”。

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Each line contains two integers, the coordinates of a single cow: X\_i and Y\_i

outputFormat: \* Line 1: A single line with a single integer that is the count of the number of times a triangle formed by the cow locations contains the origin


title: [USACO10OCT] Dinner Time S

description:
Farmer John's N (1 <= N <= 1,000) cows conveniently numbered 1..N are participating in the IOI in Bulgaria. The cows like the Bulgarian sun and are enjoying their holiday. All seems well.

This changes around dinner time. The restaurant is rather small, having only M (1 <= M <= N) cow seats conveniently numbered 1..M. Each cow starts at a location CX\_i, CY\_i (-1,000,000 <= CX\_i <= 1,000,000; -1,000,000 <= CY\_i <= 1,000,000); the seats can be found at SX\_j, SY\_j (-1,000,000 <= SX\_j <= 1,000,000; -1,000,000 <= SY\_j <= 1,000,000).

The cows have a very efficient (though primitive) method to distribute themselves into the seats. As soon as a cow is certain she will get to a seat first, she rushes there as fast as she can (all cows runs equally fast).

Farmer John's cows, like all prize cows, have no problem jumping over seats, tables, or other cows, so they can run in a straight line. When multiple cows can reach a seat at the very same time, the oldest cow (the one appearing earlier in the input data) gets the seat.  Likewise, when a cow can be the first to reach multiple seats she will also choose the one appearing earliest in the input.

Some cows won't be able to eat dinner, and those hungry cows are collectively planning to steal Farmer John's very own food. Farmer John would like a list of cows he should be wary of. (In the case when there are no hungry cows, output 0). Can you help him?

NOTE: Standard distance calculations will likely require an

intermediate result that will fit into a 64-bit integer but not into a 32-bit integer.

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..N+1: Line i+1 contains two space separated integers: CX\_i and CY\_i

\* Lines N+2..N+M+1: Line j+N+1 contains two space separated integers: SX\_j and SY\_j

outputFormat: \* Lines 1..N-M: Line i contains the number of the ith cow that Farmer John should be wary of. The cow numbers should be listed in increasing order.

translation:
## 题目描述

农场主约翰的 $N$（$1 \le N \le 10 ^ 3$）头奶牛被编号为 $1 \sim N$，它们正在保加利亚参加 IOI。奶牛们喜欢保加利亚的太阳并享受着它们的假日，一切看起来都没问题。

变化发生在晚餐时间前后。这家餐馆很小，只有 $M$（$1 \le M \le N$）个座位，编号为 $1 \sim M$。每头牛从一个位置 $CX_i$，$CY_i$ 进入餐馆（$-10 ^ 6 \le CX_i \le 10 ^ 6,-10 ^ 6 \le CY_i \le 10 ^ 6$）；座位可以在 $SX_j$，$SY_j$ 找到（$-10 ^ 6 \le SX_j \le10 ^ 6,-10 ^ 6\le SY_j\le 10 ^ 6$）。

奶牛有一种非常有效的（尽管很原始）方法把自己分配到座位上。一旦某只奶牛确定她会先到某个座位上，她就会尽快赶到那里（所有的奶牛都跑得一样快）。

农场主约翰的奶牛和所有获奖的奶牛一样，跳过座位、桌子或其他奶牛都没有问题，因此它们可以直线奔跑。当多头牛可以同时到达一个座位时，最老的牛（在输入数据中出现得更早的牛）获得座位。当一头牛可以第一个到达多个座位时，她也会选择在输入中最早出现的座位。

一些奶牛将不能吃晚饭，这些吃不到饭的饥饿的奶牛正集体计划偷农场主约翰自己的食物。农场主约翰想要一份他应该提防的奶牛名单。（如果没有饥饿的奶牛，则输出 $0$）。你能帮他吗？

注：在计算中可能会有超过 $32$ 位整数范围但在 $64$ 位整数范围内的数。

------------

## 输入格式

第一行：两个空格分隔的整数：$N$ 和 $M$。

第 $2 \sim N + 1$ 行：第 $i+1$ 行包含两个空格分隔的整数：$CX_i$ 和 $CY_i$。

第 $N+2 \sim N+M+1$ 行：行 $j+N+1$ 包含两个空格分隔的整数：$SX_j$ 和 $SY_j$。

------------

##  输出格式

第 $1$ 行到第 $(N-M)$ 行：第 $i$ 行包含农场主约翰应该提防的第 $i$ 头牛的编号。奶牛的编号应递增排序。

hint:
2 cows: Cow 1 starts at (0, 1) and cow 2 at (1, 0). There

is only 1 seat at (1, 10).

Cow 1 is closer to the seat than cow 2, so cow 1 will get the only seat.


title: [USACO10NOV] Cow Photographs G

description:
Farmer John wants to take a picture of his entire herd of N (1 <= N <= 100,000) cows conveniently numbered 1..N so he can show off to his friends.

On picture day, the cows run to form a single line in some arbitrary order with position i containing cow c\_i (1 <= c\_i <= N). Farmer John has his own ideas about how the cows should line up.

FJ thinks cow i may stand only to the left of cow i+1 (for all i, 1 <= i <= N-1) and that cow N may only stand to the left of Cow 1. Of course, no cow will stand to the left of the first (leftmost) cow in the line.

The cows are hungry for the promised post-photo dinner, so Farmer John wants to take the picture as quickly as possible. Cows are not great at following directions, so he will only choose a pair of adjacent cows and have them switch places once per minute. How quickly is Farmer John able to get them into some acceptable order?

Consider a set of 5 cows whose initial lineup looks like this:

Left           Right

3  5  4  2  1

He can first swap the second pair of cows:

3  4  5  2 1

and then swap the rightmost pair:

3  4  5  1  2

to yield an acceptable lineup that required but two minutes of cow swapping.

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains the number of the i-th cow in line: c\_i

outputFormat: \* Line 1: The minimum amount of time, in minutes, that it takes Farmer John to get the cows into some appropriate order.

translation:
FJ 希望给他的 $N(1\leq N \leq 10^5)$ 只奶牛拍照片，这样他就可以向他的朋友炫耀他的奶牛。这 $N$ 只奶牛被标号为 $1,\cdots,N$。在照相的那一天，奶牛们排成了一排。其中第 $i$ 个位置上是标号为 $c_i(1\leq c_i\leq N)$ 的奶牛。对于奶牛的站位，FJ 有他自己的想法。

FJ 是这么想的，标号为 $i(1\leq i\leq n-1)$ 的奶牛只能站在标号为 $i+1$ 的奶牛的左边，而标号为 $N$ 的奶牛只能站在标号为 $1$ 的奶牛的左边。当然，没有牛可以站在队列中最左边的奶牛的左边了。也就是说，最左边的奶牛编号是随意的。这些奶牛都非常的饿，急切的希望吃到 FJ 承诺的在拍照后的大餐，所以 FJ 想尽快的拍照。奶牛们的方向感非常的不好，所以 FJ 每一分钟只可以选择相邻的两只奶牛然后让他们交换位置。

FJ 最小需要多少时间就能使奶牛站成一个可以接受的序列？


title: [USACO10NOV] Visiting Cows G

description:
After many weeks of hard work, Bessie is finally getting a vacation! After many weeks of hard work, Bessie is finally getting a vacation!  numbered 1..N. The cows have set up quite an unusual road network with exactly N-1 roads connecting pairs of cows C1 and C2 (1 <= C1 <= N; 1 <= C2 <= N; C1 != C2) in such a way that there exists a unique path of roads between any two cows.

FJ wants Bessie to come back to the farm soon; thus, he has instructed Bessie that if two cows are directly connected by a road, she may not visit them both. Of course, Bessie would like her vacation to be as long as possible, so she would like to determine the maximum number of cows she can visit.

经过了几周的辛苦工作,贝茜终于迎来了一个假期.作为奶牛群中最会社交的牛,她希望去拜访N(1<=N<=50000)个朋友.这些朋友被标号为1..N.这些奶牛有一个不同寻常的交通系统,里面有N-1条路,每条路连接了一对编号为C1和C2的奶牛(1 <= C1 <= N; 1 <= C2 <= N; C1<>C2).这样,在每一对奶牛之间都有一条唯一的通路. FJ希望贝茜尽快的回到农场.于是,他就指示贝茜,如果对于一条路直接相连的两个奶牛,贝茜只能拜访其中的一个.当然,贝茜希望她的假期越长越好,所以她想知道她可以拜访的奶牛的最大数目.

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N: Each line describes a single road with two

space-separated integers: C1 and C2

outputFormat: \* Line 1: A single integer representing the maximum number of cows that Bessie can visit.

hint:
Bessie knows 7 cows. Cows 6 and 2 are directly connected by a road, as are cows 3 and 4, cows 2 and 3, etc. The illustration below depicts the roads that connect the cows:

1--2--3--4

|
5--6--7

Bessie can visit four cows. The best combinations include two cows on the top row and two on the bottom. She can't visit cow 6 since that would preclude visiting cows 5 and 7; thus she visits 5 and 7. She can also visit two cows on the top row: {1,3}, {1,4}, or {2,4}.


title: [USACO10NOV] Banner S

background:
题目大意(by:曹彦臣)：

平面上有(0,0)到(n,m)的(n+1)\*(m+1)个点。问有多少点对所连的线段不过其他点，且长度在[l,h]范围内。

description:
Bessie is returning from a long trip abroad, and Farmer John wants to erect a nice 'Welcome Home' banner in her pasture for her arrival. The banner will hang between two poles on a wire whose length is in the range L1..L2 (1 <= L1 <= L2; L1 <= L2 <= 1,500).

The pasture's size is W x H (1 <= W <= 1,000; 1 <= H <= 1,000), and Farmer John has installed a post at every point with integer

coordinates. Of these (W + 1) \* (H + 1) points, Farmer John must pick just two that will hold either end of the wire from which he will hang the banner.

FJ wants no interference with his banner as it hangs and requires that no post be directly under the tight wire he stretches between the two chosen posts.

Farmer John needs your help to figure out how many possible ways he can hang the banner. He knows the number is large and that a 32-bit integer might not be sufficient to compute the answer.

Consider the example pasture below, with W = 2 and H = 1:

\* \* \*
\* \* \*
The banner size is in the range 2..3. This pasture contains (2+1) \* (1+1) = 6 points and has (6 take 2) = (6\*5)/(2\*1) = 15 different potential pairs of points between which the banner-holding wire might stretch:

```cpp
(0,0)-(0,1)   (0,0)-(2,1)   (0,1)-(2,1)   (1,1)-(2,0)
(0,0)-(1,0)   (0,1)-(1,0)   (1,0)-(1,1)   (1,1)-(2,1)
(0,0)-(1,1)   (0,1)-(1,1)   (1,0)-(2,0)   (2,0)-(2,1)
(0,0)-(2,0)   (0,1)-(2,0)   (1,0)-(2,1)
```
Of these pairs, only four have a length in the range 2..3:
Len                       Len

(0,0)-(2,0) 2.00          (0,1)-(2,0) 2.24

(0,0)-(2,1) 2.24          (0,1)-(2,1) 2.00

Of these four, the pairs (0,0)-(2,0) and (0,1)-(2,1) both have a post directly on the line between the endpoints, and thus are

unsuitable.

So, just two pairs of points out of 15 are acceptable candidates for hanging the banner wire.

inputFormat: \* Line 1: Four space-separated integers: W, H, L1, and L2

outputFormat: \* Line 1: A single integer denoting the number of possible banners

translation:
贝西正要从一趟长途旅行中回来，Farmer John想要在她的牧场里布置一个“欢迎回家”的横幅来迎接她。这个横幅将会拴在一个范围为L1到L2 (1 <= L1 <= L2; L1 <= L2 <= 1,500)的线的两端

牧场面积为W × H (1 <= W <= 1000;1 <= H <= 1000)，并且Farmer John在每个整数坐标的点都安装了一个杆子。在这(W + 1) * (H + 1)点中，Farmer John必须选择两个点来固定他将悬挂旗帜的线的两端。

FJ希望他的旗帜挂上去之后不会被挡住，所以在两个柱子之间的线上不能有其他柱子。

Farmer John需要你的帮助来计算出他有多少种可能的方式来悬挂横幅。他知道这个数字很大，一个32位的整数可能不足以计算出答案。

示例，W = 2, H = 1: 横幅大小在2到3的范围内。这个牧场包含(2+1)(1+1)= 6个点，并且有(6选2)=(65)/(2*1)= 15个不同的潜在点对，在这些点之间可以拉出这几条线:

(0,0)-(0,1)   (0,0)-(2,1)   (0,1)-(2,1)   (1,1)-(2,0)
(0,0)-(1,0)   (0,1)-(1,0)   (1,0)-(1,1)   (1,1)-(2,1)
(0,0)-(1,1)   (0,1)-(1,1)   (1,0)-(2,0)   (2,0)-(2,1)
(0,0)-(2,0)   (0,1)-(2,0)   (1,0)-(2,1)
在这些对中，只有四个的长度在2..3的范围内:

(0,0)-(2,0) 2.00

(0,1)-(2,0) 2.24

(0,0)-(2,1) 2.24

(0,1)-(2,1) 2.00

在这四个中，(0,0)-(2,0)和(0,1)-(2,1)在端点之间的直线上都有一个柱子，因此是不合适的。

所以，15对点中只有两对点可以作为悬挂横幅线的候选点。


title: [USACO10NOV] Candy S

description:
Farmer John knows that Bessie loves to eat candy. FJ has N (1 <= N <= 40,000) candies that he wants to give Bessie over some number of days. Each day, Farmer John gives Bessie a choice of how many candies she chooses to eat that day by choosing the number from a master list FJ supplies that has Nopt (1 <= Nopt <= 50) different options, C\_i (1 <= C\_i <= N). She must take exactly C\_i candies, no more, no less.

Farmer John has also disclosed F (1 <= F <= 50) of his favorite numbers, FN\_i (1 <= FN\_i <= N). Whenever the number of candies remaining at the end of the day precisely matches one of these favorite numbers, Bessie has the option to have him add exactly M (1 <= M <= 100) more candies to the candy supply. Bessie might get another option to add M candies several times if adding candies creates another favorite number. In the best circumstances, Bessie can obtain an infinite amount of candy!

When Bessie cannot choose some amount of candy to take (because there is not enough), and the number of candies remaining is not any of FJ's favorite numbers, she cannot have any more candy.

Unfortunately, Bessie cannot think ahead as far as she'd like to, so she needs your help in order to eat as many candies as possible.

By way of example, consider this scenario:

\* Farmer John's basket initially contains 10 candies

\* Bessie can chose to eat either 3 or 5 candies each day

\* Farmer John will add 1 candy any time the remaining number of candies is 2 or 4

Bessie could use this set of choices to maximize the amount of candy she can eat:

```cpp

                  Initial      # Candies   Remaining     Bonus     Final
        Day      # Candies       Eaten      Candies     Candies   Candies

         1          10             3          7            0        7
         2           7             3          4            1        5
         3           5             3          2            1        3
         4           3             3          0            0        0

```

Total candies eaten = 3 + 3 + 3 + 3 = 12.

农民约翰知道Bessie喜欢吃糖果。约翰有N（1≤N≤40000）的糖果，他想给Bessie几天。每一天，贝茜从一个列表（有nopt（1 <= nopt <= 50）种不同的选择），选择那一天吃掉刚好C\_i（1 <= c\_i <= N）个糖果。

农民约翰也透露F（1≤f≤50）他最喜欢的数字，FN\_i（1 <= FN\_i <= N）。当当天最后剩下的糖果数量精确匹配其中一个喜欢的号码，Bessie可以让他添加恰好M（1 <= M = 100）个糖果。如果加后得到的个数，还是FJ喜欢的数字，就可以继续添加糖果M个（加几次由贝西决定）。在最好的情况下，Bessie可以吃掉无限量的糖果！

当Bessie不能选择一定量的糖（因为没有足够的），或者糖果的剩余数量不是任何约翰最喜欢的号码，她不能有任何更多的糖果。

不幸的是，Bessie想不出她想做的事，所以她需要你的帮助才能吃尽可能多的糖果。

inputFormat:
\* Line 1: Four space-separated integers: N, Nopt, F, and M

\* Lines 2..Nopt+1: Line i+1 contains a single integer: C\_i

\* Lines Nopt+2..Nopt+F+1: Line i+Nopt+1 contains a single integer: FN\_i

1行：四个整数N，Nopt，F和M

2行。nopt + 1：i+ 1行包含一个整数：c\_i

nopt + 2 .. nopt + F + 1 + 1 + nopt行：行包含一个整数：fn\_i

outputFormat:
\* Line 1: A single integer, denoting the maximum amount of candies Bessie can eat, or -1 if  Bessie can eat an infinite amount of candy.

1行：一个整数，表示Bessie最多可以吃几个。如果Bessie可以无限量吃糖输出-1。

hint: 感谢@ 王彦梓 提供翻译，kkksc03进行了修正。


title: [USACO10NOV] Chocolate Milk S

description:
Farmer John's milk production and shipping system is an intricate one! He uses milking machines for his many cows to harvest the milk that then flows into pipes.

Each of these pipes connects a milking machine to a joint, where it might be joined by exactly one more pipe (the milk flowing through both pipes merges). The milk then flows through additional pipes (which all start and end at joints) until it reaches the long central pipe connecting to the distribution room.

The milk then goes through a reverse process of splitting at various joints until it is flows into milk tanks that are picked up and taken to market.

Farmer John notices that there is at most one way for milk to travel from one joint to any other joint. Furthermore, since Farmer John is an efficient man by nature, he has made sure that milk will flow through each and every pipe; in other words, no pipe is unneeded.

If we think of a milking machine, joint, or milk tank as a node, there are N (2 <= N <= 100,000) nodes in total (and N-1 pipes

connecting them). The input describes each pipe as an ordered pair of nodes, A\_i (1 <= A\_i <= N) and B\_i (1 <= B\_i <= N; A\_i < B\_i) indicating milk flows from node A\_i to node B\_i. If there is no pipe coming in to A\_i, it is a milking machine. Likewise, if no pipe goes out from B\_i, it is a tank.

The demand of chocolate milk has skyrocketed in recent months, and Farmer John wants to install a chocolate inserter at one of the joints so he can create delicious chocolate milk for customers.

Being thrifty, Farmer John has only bought one chocolate inserter, so he wants to place it at a joint through which all the milk passes. He knows that such a joint exists.

Help Farmer John find all the possible places he can install the chocolate inserter.  (Note that Farmer John cannot install the chocolate inserter at the same location as a milking machine.)

As an example, consider a milking setup like this one:

```cpp

           1 ----+
                 |
                 v
           2 --> 4 --> 6 ------------------> 7 --> 8
                       ^                     |
                       |                     |
           3 --> 5 ----+                     + --> 9

```
Visual inspection shows that the chocolate inserter can be installed at either joint 6 or 7, as all milk flows through those joints.

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N: Line i+1 contains two space-separated integers that describe a pipe's connectivity: A\_i and B\_i

outputFormat: \* Lines 1..??: Integers, one per line and in ascending order, each denoting a possible joint at which to install the chocolate inserter.

translation:
### 题目描述
农民约翰的牛奶生产和运输是一个复杂的过程，他用挤奶器给他的那么多头奶牛挤奶，然后流入管道。

每一个管道把一台挤奶器和一个可能连有一台或多台挤奶器的接口连接起来（这样几个管道里的牛奶就汇合了）。然后牛奶流入附加管道（连在各个接口之间的管道）直到流到中央管道，通向储存室。 然后这些牛奶又经历一个逆向的过程通过管道分流到各个牛奶桶，最后被运至市场。

约翰发现对于牛奶来说，最多只有一种方式从一个接口流到另一个接口。并且由于约翰是一个高效率的人，他需要确保每一个管道都有牛奶经过，也就是说，没有多余的管道。

如果我们把每个挤奶机、接口和奶罐都看成一个节点，就共有 $N$ 个节点，输入有序的节点对 $A_{i}$ 和 $B_{i}$ ，代表牛奶从 $A_{i}$ 节点流到 $B_{i}$ 节点，如果没有相对应的父节点，那就说明这是一个挤奶器，同样的如果没有对应的尾节点，则这是一个奶罐。

这几个月巧克力牛奶的需求量激增，所以约翰想要在某一个接口处安装一个巧克力混合器以得到巧克力牛奶，为了节约，约翰只买了一个巧克力混合器。所以他想把这个东西放到一个所有牛奶都能经过的接口，事实上，有这种接口存在。

帮助约翰找到这样的节点（注意：不能把巧克力混合器放在挤奶机里）。
```

           1 ----+
                 |
                 v
           2 --> 4 --> 6 ------------------> 7 --> 8
                       ^                     |
                       |                     |
           3 --> 5 ----+                     + --> 9

```
所有的牛奶都会流经6号或7号节点，所以巧克力混合器可以放在这两个节点上。

### 输入格式
第 $1$ 行一个整数 $N$。

第 $2$ 到第 $N$ 行：包含空格分隔的两个整数，描述第 $i$ 个管道连接的两个节点：$A_{i}$ 和 $B_{i}$。

### 输出格式
第 $1$ 行到 ？？行：每行一个整数，升序输出每个可以安装巧克力混合器的节点。


title: [USACO10DEC] Cow Calisthenics G

description:
Farmer John continues his never-ending quest to keep the cows fit by having them exercise on various cow paths that run through the pastures. These cow paths can be represented as a set of vertices connected with bidirectional edges so that each pair of vertices has exactly one simple path between them. In the abstract, their layout bears a remarkable resemblance to a tree. Surprisingly, each edge (as it winds its way through the pastures) has the same length.

For any given set of cow paths, the canny cows calculate the longest possible distance between any pair of vertices on the set of cowpaths and call it the pathlength. If they think this pathlength is too large, they simply refuse to exercise at all.

Farmer John has mapped the paths and found V (2 <= V <= 100,000) vertices, conveniently numbered from 1..V. In order to make shorter cowpaths, he can block the path between any two vertices, thus creating more sets of cow paths while reducing the pathlength of both cowpath sets.

Starting from a single completely connected set of paths (which have the properties of a tree), FJ can block S (1 <= S <= V-1) paths, creating S+1 sets of paths. Your goal is to compute the best paths he can create so that the largest pathlength of all those sets is minimized.

Farmer John has a list of all V-1 edges in his tree, each described by the two vertices A\_i (1 <= A\_i <= V) and B\_i (1 <= B\_i <= V; A\_i != B\_i) that it connects.

Consider this rather linear cowpath set (a tree with 7 vertices):

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

If FJ can block two paths, he might choose them to make a map like this:

1---2 | 3---4 | 5---6---7
where the longest pathlength is 2, which would be the answer in this case. He can do no better than this.

TIME LIMIT: 2 seconds

MEMORY LIMIT: 32 MB

Farmer John为了保持奶牛们的健康，让可怜的奶牛们不停在牧场之间 的小路上奔跑。这些奶牛的路径集合可以被表示成一个点集和一些连接 两个顶点的双向路，使得每对点之间恰好有一条简单路径。简单的说来， 这些点的布局就是一棵树，且每条边等长，都为1。 对于给定的一个奶牛路径集合，精明的奶牛们会计算出任意点对路径的最大值， 我们称之为这个路径集合的直径。如果直径太大，奶牛们就会拒绝锻炼。 Farmer John把每个点标记为1..V (2 <= V <= 100,000)。为了获得更加短 的直径，他可以选择封锁一些已经存在的道路，这样就可以得到更多的路径集合， 从而减小一些路径集合的直径。 我们从一棵树开始，FJ可以选择封锁S (1 <= S <= V-1)条双向路，从而获得 S+1个路径集合。你要做的是计算出最佳的封锁方案，使得他得到的所有路径集合 直径的最大值尽可能小。 Farmer John告诉你所有V-1条双向道路，每条表述为：顶点A\_i (1 <= A\_i <= V) 和 B\_i (1 <= B\_i <= V; A\_i!= B\_i)连接。

inputFormat:
\* Line 1: Two space separated integers: V and S

\* Lines 2..V: Two space separated integers: A\_i and B\_i

outputFormat: \* Line 1: A single integer that is the best maximum pathlength FJ can achieve with S blocks


title: [USACO10DEC] Big Macs Around the World G

description:
Bessie is studying her favorite subject, Macroeconomics, in cowllege. For her final project, she will be presenting research on exchange rates between countries around the world.

In order to make her presentation more lively, she would like to show the relative prices of Big Macs around the world, despite their rather unsavory contents. To illustrate, suppose that Bessie would like to find smallest value of a Big Mac in a country given its value in some initial country and exchange rates from which other country's values can be calculated (as illustrated below):

```cpp
* A Big Mac is worth 60 dollars in the United States
* The exchange rate from US dollars to Canadian dollars is 0.2 Canadian dollars per US dollar
* The exchange rate from US dollars to British Pounds is 5.00 British Pounds per US Dollar
* The exchange rate from British Pounds to Canadian dollars is 0.5 Canadian dollars per British Pound
* The exchange rate between Canadian dollars to US dollars is 5.00 US dollars per Canadian dollar and Bessie would like to find the smallest possible value of a Big Mac in Canada that can be obtained by exchanging currencies. There are two ways:
* Going from US dollars directly to Canada dollars would yield a burger worth 60.00 US dollars * 0.2 Canadian dollars / US dollar = 12.00 Canadian dollars
* Going from US dollars to British Pounds to Canadian dollars would yield a burger worth 60.00 US$ * 5.00 GBP / 1 US$ * 0.5 C$ / 1 GBP = 150.00 C$ (Canadian dollars).
```
Bessie would choose the former option, since she would much rather pay 12.00 Canadian dollars instead of 150.00 Canadian dollars for a Big Mac in Canada.

Bessie has N (1 <= N <= 2,000) countries conveniently labeled 1 to N that she would like to consider along with a list of M (1 <= M <= 25,000) exchange rates e_ij (0.1 < e_ij <= 10), each between countries i and j (1 <= i <= N; 1 <= j <= N).

Given the value V (1 <= V <= 1,000,000,000,000), which is not necessarily an integer, of the Big Mac in her starting country A (1 <= A <= N), help her find the smallest possible value of a Big Mac in country B (1 <= B <= N; B != A) after a series of currency conversions. If there is no minimum, output 0.

It is guaranteed that the answer is, if not 0, between 1 and 10^15.

It is also guaranteed that, for any country's currency, it is possible to get to any other country's currency.

inputFormat:
Line 1: Five space-separated numbers: N, M, V, A, B

Lines 2..M+1: Three space-separated numbers: i, j, e\_ij

outputFormat: Line 1: A single positive number, the price of the Big Mac, with absolute or relative error at most 10^-6. If there is no minimum, output 0.

translation:
### 题目描述

Bessie 正在学习她最喜欢的科目宏观经济学，作为她最后一门学科，她将对世界各种货币的汇率进行研究。

为了让她的演讲更加生动，她会展示一个叫做 BM 的商品在全世界的相对价格。举个例子，Bessie 会通过其他国家的汇率去找到一件 BM 在一个国家的最小价值。

- 一件 BM 在美国值 $60$ 美元；
- 美元与加拿大元的汇率为 $1$ 美元换 $0.2$ 加拿大元（$1:0.2$）。
- 美元与英镑的汇率为 $1$ 美元换 $5$ 英镑（$1:5$）。
- 英镑与加拿大元的汇率为 $1$ 英镑换 $0.5$ 加拿大元（$1:0.5$）。
- 加拿大元与美元的汇率是 $5$ 美元换一加拿大元（$5:1$），Bessie 有两种方法通过货币兑换在加拿大这个国家找到一件 BM 的最低价值：

1. 拿着美元直接去加拿大，通过汇率得出一件 BM 只要 $12$ 加拿大元；
2. 拿着美元去英国，兑换为英镑后再去加拿大，得出一件 BM 要 $150$ 加拿大元。

Bessie 会选择前一种方案因为她更乐意为在加拿大买一件 BM 支付 $12$ 加元而不是 $150$ 加元。

Bessie 有 $N(1\leq N\leq 2000)$ 个国家的信息和 $M(1\leq M\leq25000)$ 种汇率，在 $i,j$ 国间的汇率表示为 $e_{ij}(0.1\leq e_{ij}\leq 10)$。

给你一个值 $V(1\leq V\leq 10^{12})$，$V$ 不一定是一个整数。$V$ 是 BM 在起始国家 A 的价格，帮助 Bessie 寻找到在 B 国 BM 最低的价格，如果不存在，则输出 $0$。

据保证答案小于 $10^{15}$，也保证所有国家都可以通过汇率将钱币转为别的国家的。

### 输入格式

第 $1$ 行：五个数：$N,M,V,A,B$，分别一个空格隔开。

第 $2$ 到 $M+1$ 行：三个数 $i,j,e_{ij}$，分别一个空格隔开。

### 输出格式

一行：BM 在 B 国的最低价格，精确到 $10^{-6}$。如果没有最小值，输出 $0$。

**注意，本题的汇率是单向的**。

感谢 @JJYZ\_cbh 的耐心翻译


title: [USACO10DEC] Threatening Letter G

description:
FJ has had a terrible fight with his neighbor and wants to send him a nasty letter, but wants to remain anonymous. As so many before him have done, he plans to cut out printed letters and paste them onto a sheet of paper. He has an infinite number of the most recent issue of the Moo York Times that has N (1 <= N <= 50,000) uppercase letters laid out in a long string (though read in as a series of shorter strings). Likewise, he has a message he'd like to compose that is a single long string of letters but that is read in as a set of shorter strings.

Being lazy, he wants to make the smallest possible number of cuts. FJ has a really great set of scissors that enables him to remove any single-line snippet from the Moo York Times with one cut. He notices that he can cut entire words or phrases with a single cut, thus reducing his total number of cuts.

What is the minimum amount of cuts he has to make to construct his letter of M (1 <= M <= 50,000) letters?

It is guaranteed that it is possible for FJ to complete his task.

Consider a 38 letter Moo York Times:

```cpp
THEQUICKBROWNFOXDO
GJUMPSOVERTHELAZYDOG
from which FJ wants to construct a 9 letter message:
FOXDOG
DOG
```
These input lines represent a pair of strings:
THEQUICKBROWNFOXDOGJUMPSOVERTHELAZYDOG

FOXDOGDOG

Since 'FOXDOG' exists in the newspaper, FJ can cut this piece out and then get the last 'DOG' by cutting out either instance of the word 'DOG'.

Thus, he requires but two cuts.

FJ 刚刚和邻居发生了一场可怕的争吵，他咽不下这口气，于是决定佚名发给他的邻居一封脏话连篇的信。他有无限张完全相同的已经打印好的纸张，都包含 $N$ 个字母。他有一把举世无双的剪刀，可以从某张纸中通过一刀剪出连续的一段（也可以通过一刀获得整个字符串）。他想知道获得这封 $M$ 个字母的长信最少需要剪多少刀。保证这总是可能的。

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..?: N letters laid out on several input lines; this is the text of the one copy of the Moo York Times. Each line will have no more than 80 characters.

\* Lines ?..?: M letters that are the text of FJ's letter. Each line will have no more than 80 characters.

outputFormat: \* Line 1: The minimum number of cuts FJ has to make to create his message

samples:
38 9
THEQUICKBROWNFOXDO
GJUMPSOVERTHELAZYDOG
FOXDOG
DOG


title: [USACO10DEC] Apple Delivery S

description:
Bessie has two crisp red apples to deliver to two of her friends in the herd. Of course, she travels the C (1 <= C <= 200,000)

cowpaths which are arranged as the usual graph which connects P (1 <= P <= 100,000) pastures conveniently numbered from 1..P: no cowpath leads from a pasture to itself, cowpaths are bidirectional, each cowpath has an associated distance, and, best of all, it is always possible to get from any pasture to any other pasture. Each cowpath connects two differing pastures P1\_i (1 <= P1\_i <= P) and P2\_i (1 <= P2\_i <= P) with a distance between them of D\_i. The sum of all the distances D\_i does not exceed 2,000,000,000.

What is the minimum total distance Bessie must travel to deliver both apples by starting at pasture PB (1 <= PB <= P) and visiting pastures PA1 (1 <= PA1 <= P) and PA2 (1 <= PA2 <= P) in any order. All three of these pastures are distinct, of course.

Consider this map of bracketed pasture numbers and cowpaths with distances:

```cpp
               3        2       2
           [1]-----[2]------[3]-----[4]
             \     / \              /
             7\   /4  \3           /2
               \ /     \          /
               [5]-----[6]------[7]
                    1       2
```
If Bessie starts at pasture [5] and delivers apples to pastures [1] and [4], her best path is:

5 -> 6-> 7 -> 4\* -> 3 -> 2 -> 1\*

with a total distance of 12.

inputFormat:
\* Line 1: Line 1 contains five space-separated integers: C, P, PB, PA1, and PA2

\* Lines 2..C+1: Line i+1 describes cowpath i by naming two pastures it connects and the distance between them: P1\_i, P2\_i, D\_i

outputFormat: \* Line 1: The shortest distance Bessie must travel to deliver both apples

translation:
贝西有两个又香又脆的红苹果要送给她的两个朋友。当然她可以走的 $C(1 \le C \le 200000)$ 条“牛路”都被包含在一种常用的图中。这张图同时包含了$P(1 \le P \le 100000)$ 个牧场，分别被标为 $1 \cdots P$。没有“牛路”会从一个牧场又走回它自己。“牛路”是双向的，每条牛路都会被标上一个距离。最重要的是，每个牧场都可以通向另一个牧场。每条牛路都连接着两个不同的牧场 $P1\_i$和$P2\_i$（$1 \le P1\_i,P2\_i \le P$)，距离为$D\_i$。所有“牛路”的距离之和不大于 $2000000000$。

现在，贝西要从牧场 $PB$ 开始给 $PA\_1$ 和 $PA\_2$ 牧场各送一个苹果（$PA\_1$ 和 $PA\_2$ 顺序可以调换），那么最短的距离是多少呢？当然，$PB$、$PA\_1$ 和 $PA\_2$ 各不相同。


title: [USACO10DEC] Treasure Chest S

description:
Bessie and Bonnie have found a treasure chest full of marvelous gold coins! Being cows, though, they can't just walk into a store and buy stuff, so instead they decide to have some fun with the coins.

The N (1 <= N <= 5,000) coins, each with some value C\_i (1 <= C\_i <= 5,000) are placed in a straight line. Bessie and Bonnie take turns, and for each cow's turn, she takes exactly one coin off of either the left end or the right end of the line. The game ends when there are no coins left.

Bessie and Bonnie are each trying to get as much wealth as possible for themselves. Bessie goes first. Help her figure out the maximum value she can win, assuming that both cows play optimally.

Consider a game in which four coins are lined up with these values:

30  25  10  35

Consider this game sequence:

Bessie    Bonnie       New Coin

Player   Side   CoinValue   Total     Total         Line

Bessie   Right     35        35         0       30  25  10

Bonnie   Left      30        35        30         25  10

Bessie   Left      25        60        30           10

Bonnie   Right     10        60        40           --

This is the best game Bessie can play.

小 A 和小 B 在玩游戏。

初始时，有 $n$ 个硬币被摆成了一行，从左至右数第 $i$ 个硬币的价值为 $c_i$。

小 A 和小 B 每人一回合，在一个人的回合中，他可以选择**当前**硬币序列最左侧或者最右侧的硬币，并将他从序列中取出，将其价值累加到自己获得的累计价值中，然后进行另一个人的回合。当硬币全部被取走时，游戏结束。

请求出在双方都尽可能的使自己累计价值最大的情况下，若由小 A 进行第一回合，那么他能获得的累计价值最大是多少。

inputFormat:
输入的第一行是一个整数 $n$，代表硬币的个数。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 个硬币的价值 $c_i$。

outputFormat: 输出一行一个整数，代表小 A 能获得的最大累计价值。

hint:
#### 输入输出样例 $1$ 解释

初始时，硬币序列为 $\{30,~25,~10,~35\}$。

第一回合，小 A 取走最右侧的硬币，序列变为 $\{30,~25,~10\}$，小 A 的累加价值为 $35$。

第二回合，小 B 取走最左侧的硬币，序列变为 $\{25,~10\}$，小 B 的累加价值为 $30$。

第三回合，小 A 取走最左侧的硬币，序列变为 $\{10\}$，小 A 的累加价值为 $35 + 25 = 60$。

第四回合，小 B 取走最左侧的硬币，序列变为空，小 B 的累加价值为 $30 + 10 = 40$，游戏结束。

小 A 获得的最大累计价值为 $60$。

#### 数据范围与约定

对于全部的测试点，$1 \leq n \leq 5 \times 10^3$，$1 \leq c_i \leq 5 \times 10^3$。

**提示：请注意，本题的空间限制为 $64$ Mib。**


title: [USACO10DEC] The Trough Game S

description:
Farmer John and Bessie are playing games again. This one has to do with troughs of water.

Farmer John has hidden N (1 <= N <= 20) troughs behind the barn, and has filled some of them with food. Bessie has asked M (1 <= M <= 100) questions of the form, 'How many troughs from this list (which she recites) are filled?'.

Bessie needs your help to deduce which troughs are actually filled.

Consider an example with four troughs where Bessie has asked these questions (and received the indicated answers):

1) 'How many of these troughs are filled: trough 1' -->  1 trough is filled

2) 'How many of these troughs are filled: troughs 2 and 3' -->  1 trough is filled

3) 'How many of these troughs are filled: troughs 1 and 4' -->  1 trough is filled

4) 'How many of these troughs are filled: troughs 3 and 4' -->  1 trough is filled

From question 1, we know trough 1 is filled.

From question 3, we then know trough 4 is empty.

From question 4, we then know that trough 3 is filled.

From question 2, we then know that trough 2 is empty.

农夫约翰和贝西又在玩游戏。这个游戏需要很多个槽。

农夫约翰在谷仓里藏起来了N（1<=N<=20）个槽，并且他已经把其中的一些装上了食物。贝西以“在这个表里（表由贝西提供）有多少个槽里有食物？”的形式问了M（1<=M<=100）个问题。

现在，贝西想知道，哪几个槽里有食物？

这里有一个样例：

（1）在第一个槽里有多少个槽里有食物？——1个

（2）在第二个和第三个槽里有多少个槽里有食物？——1个

（3）在第一个和第四个槽里有多少个槽里有食物？——1个

（4）在第三个和第四个槽里有多少个槽里有食物？——1个

从第一个问题可以知道，第一个槽是有食物的。

从第二个问题可以知道，第四个槽是没有食物的。

从第三个问题可以知道，第三个槽是有食物的。

从第四个问题可以知道，第二个槽是没有食物的。

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..M+1: A subset of troughs, specified as a sequence of contiguous N 0's and 1's, followed by a single integer that is the number of troughs in the specified subset that are filled.

outputFormat:
\* Line 1: A single line with:

\* The string 'IMPOSSIBLE' if there is no possible set of filled troughs compatible with Farmer John's answers.

\* The string 'NOT UNIQUE' if Bessie cannot determine from the given data exactly what troughs are filled.

\* Otherwise, a sequence of contiguous N 0's and 1's specifying which troughs are filled.


title: [USACO11JAN] Bottleneck G

description:
Farmer John is gathering the cows. His farm contains a network of N (1 <= N <= 100,000) fields conveniently numbered 1..N and connected by N-1 unidirectional paths that eventually lead to field 1. The fields and paths form a tree.

Each field i > 1 has a single one-way, exiting path to field P\_i, and currently contains C\_i cows (1 <= C\_i <= 1,000,000,000). In each time unit, no more than M\_i (0 <= M\_i <= 1,000,000,000) cows can travel from field i to field P\_i (1 <= P\_i <= N) (i.e., only M\_i cows can traverse the path).

Farmer John wants all the cows to congregate in field 1 (which has no limit on the number of cows it may have). Rules are as follows:

\* Time is considered in discrete units.

\* Any given cow might traverse multiple paths in the same time unit. However, no more than M\_i total cows can leave field i (i.e., traverse its exit path) in the same time unit.

\* Cows never move \*away\* from field #1.

In other words, every time step, each cow has the choice either to

a) stay in its current field

b) move through one or more fields toward field #1, as long as the bottleneck constraints for each path are not violated

Farmer John wants to know how many cows can arrive in field 1 by certain times. In particular, he has a list of K (1 <= K <= 10,000) times T\_i (1 <= T\_i <= 1,000,000,000), and he wants to know, for each T\_i in the list, the maximum number of cows that can arrive at field 1 by T\_i if scheduled to optimize this quantity.

Consider an example where the tree is a straight line, and the T\_i list contains only T\_1=5, and cows are distibuted as shown:

```cpp
Locn:      1---2---3---4      <-- Pasture ID numbers
C_i:       0   1   12  12     <-- Current number of cows
M_i:           5   8   3      <-- Limits on path traversal; field 1 has no limit since it has no exit
The solution is as follows; the goal is to move cows to field 1:
```
Tree:      1---2---3---4
```cpp
t=0        0   1   12  12     <-- Initial state
t=1        5   4   7   9      <-- field 1 has cows from field 2 and 3 t=2        10  7   2   6
t=3        15  7   0   3
t=4        20  5   0   0
t=5        25  0   0   0
Thus, the answer is 25: all 25 cows can arrive at field 1 by time t=5.

inputFormat:
\* Line 1: Two space-separated integers: N and K

\* Lines 2..N: Line i (not i+1) describes field i with three

space-separated integers: P\_i, C\_i, and M\_i

\* Lines N+1..N+K: Line N+i contains a single integer: T\_i

outputFormat: \* Lines 1..K: Line i contains a single integer that is the maximum number of cows that can arrive at field 1 by time T\_i.

translation:
WC正在召集奶牛,他的农场有一个包含 ***N*** 块农田的网络，编号为 **1 -- N** ，每个农场里有 $C_i$ 头牛。农场被 **N-1**  条 **单向** 边链接,（每个农场有通向$P_i$的路） 保证从任何点可以到达1号点。WC想让所有奶牛集中到1号农场。

**时间是离散的** 奶牛可以在1单位时间里走过任意多条道路，但是每条路有一个容纳上限 *$M_i$*  并且奶牛不会离开1号农场(农场没有容量上限)

### 每一个单位时间，奶牛可以选择如下几种行动
1. 留在当前的农场
2. 经过几条道路，向1号农场移动（需要满足$M_i$）

WC想要知道有多少牛可以在某个特定的时刻到达1号农场，
他有一张列着 ***K*** 个时间（分别为$T_i$)的单子
，他想知道在每个$T_i$, 采用最优策略在$T_i$结束最多能有多少牛到1号农场

### 数据范围如下：
$1 \le N \le  10^5$

$1 \le C_i \le  10^9$

$0 \le M_i \le 10^9$

$1 \le P_i \le N$

$1 \le K \le 10^4$

$1 \le T_i \le 10^9$

## **输入输出格式**
* 输入格式

    *第一行：两个整数 N 和 K

    *第2—N行，第i行描述一块农场及它的路 $P_i \;C_i\;M_i$

    *第N+1 - N+K行， 第N+i 一个整数 $T_i$
* 输出格式

    *每行一个答案对应$T_i$

感谢@ToBiChi 提供翻译


title: [USACO11JAN] The Continental Cowngress G

description:
Displeased with Farmer John's leadership, the cows have seceded from the farm and have formed the first Continental Cowngress. Built on the principle of 'every cow gets something they want,' they've decided on the following voting system:

The M (1 <= M <= 4000) cows in attendance will vote on  N (1 <= N <= 1,000) legislative bills. Each cow casts a 'yes' or 'no' vote (denoted as 'Y' or 'N' in the input file) on exactly two (distinct) bills B\_i and C\_i (1 <= B\_i <= N; 1 <= C\_i <= N). The votes are called VB\_i (VB\_i in {'Y', 'N'}) and VC\_i (VC\_i in {'Y', 'N'}) respectively.

Finally, the bills are to be passed or not in such a way that every cow gets her way on at least one of her votes. For example, if Bessie votes 'yes' on Bill 1, and 'no' on Bill 2, then in any valid solution, it must be the case that either Bill 1 gets passed or Bill 2 gets rejected (or both).

Given the votes of each of the cows, it's your job to figure out which bills will be passed and which bills will be rejected in order to conform to the rules above.  If there is no solution, print 'IMPOSSIBLE'. If there is at least one solution, then for each bill, display:

Y  if in every solution this bill passes

N  if in every solution this bill fails

?  if there are solutions where this bill passes and solutions where it does not pass

Consider the following set of votes (two for each cow):
```
- - - - - BILL - - - - -

1        2        3

Cow 1   YES      NO

Cow 2   NO       NO

Cow 3   YES               YES

Cow 4   YES      YES
```
From this, two solutions satisfy every cow:

\* Bill 1 passes (this then satisfies cows 1, 3, and 4)

\* Bill 2 fails (this then satisfies cow 2)

\* Bill 3 could pass or fail (and this is the reason there are two solutions)

In fact, these are the only two solutions, so the answer is the three character string below:

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..M+1: Line i+1 describes cow i's votes with four

space-separated fields -- an integer, a vote, another integer, and another vote: B\_i, VB\_i, C\_i, VC\_i

outputFormat:
\* Line 1: A string with N characters, where the ith character is either a 'Y' if the ith bill must pass, an 'N' if the ith bill must fail, or a '?' if it cannot be determined whether the bill passes from these votes.

If there is no solution which satisfies every cow, then output the single line 'IMPOSSIBLE'.

translation:
> 简述 :
> 给出 $n$ 个法案， $m$ 头牛的意见， 每头牛会表决两次。
>每次表决格式为 `i Y` 表示“支持 $i$ 号法案”或 `i N` 表示“反对 $i$ 号法案”。
> 最终，每头牛至少要有一个表决被满足。不可能成立的话输出 `IMPOSSIBLE`，否则输出方案。

由于对 Farmer John 的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。

议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统： $M$只到场的奶牛 ( $1\le M\le 4000$ ) 会给 $N$ 个议案投票 ( $1\le N\le 1,000$ ) 。每只奶牛会对恰好两个议案 $B_i$ 与 $C_i$ ( $1\le B_i \le N$ ; $1 \le C_i \le N$ ) 投出“是”或“否”（输入文件中的 `Y` 和 `N` ）。

他们的投票结果分别为 $V_{B_i}$ ( $V_{B_i} \in \{ \texttt{Y}, \texttt{N}\})$ 与 $V_{C_i} (V_{C_i} \in \{\texttt{Y}, \texttt{N}\})$。 最后，法案会以如下的方式决定：每只奶牛投出的两票中至少有一票和最终结果相符合。 例如 Bessie 给法案 $1$ 投了赞成 `Y`，给法案 $2$ 投了反对 `N`，那么在任何合法的法案通过方案中，必须满足法案 $1$ 必须是 `Y`或者议案 $2$ 必须是 `N`（或者同时满足）。

你的工作是确定哪些法案可以通过，哪些不能。

如果不存在这样一个方案， 输出 `IMPOSSIBLE`。

如果至少有一个解，对于每个法案输出：

 - `Y` 如果在每个解中，这个法案都必须通过。
 - `N` 如果在每个解中，这个法案都必须驳回。
 - `?` 如果有的解这个法案可以通过，有的解中这个法案会被驳回。


title: [USACO11JAN] Roads and Planes G

description:
Farmer John is conducting research for a new milk contract in a new territory. He intends to distribute milk to T (1 <= T <= 25,000) towns conveniently numbered 1..T which are connected by up to R (1 <= R <= 50,000) roads conveniently numbered 1..R and/or P (1 <= P <= 50,000) airplane flights conveniently numbered 1..P.

Either road i or plane i connects town A\_i (1 <= A\_i <= T) to town B\_i (1 <= B\_i <= T) with traversal cost C\_i. For roads, 0 <= C\_i <= 10,000; however, due to the strange finances of the airlines, the cost for planes can be quite negative (-10,000 <= C\_i <= 10,000).

Roads are bidirectional and can be traversed from A\_i to B\_i or B\_i to A\_i for the same cost; the cost of a road must be non-negative.

Planes, however, can only be used in the direction from A\_i to B\_i specified in the input. In fact, if there is a plane from A\_i to B\_i it is guaranteed that there is no way to return from B\_i to A\_i with any sequence of roads and planes due to recent antiterror regulation.

Farmer John is known around the world as the source of the world's finest dairy cows. He has in fact received orders for his cows from every single town. He therefore wants to find the cheapest price for delivery to each town from his distribution center in town S (1 <= S <= T) or to know that it is not possible if this is the case.

MEMORY LIMIT: 64MB

inputFormat:
\* Line 1: Four space separated integers: T, R, P, and S

\* Lines 2..R+1: Three space separated integers describing a road: A\_i, B\_i and C\_i

\* Lines R+2..R+P+1: Three space separated integers describing a plane: A\_i, B\_i and C\_i

outputFormat: \* Lines 1..T: The minimum cost to get from town S to town i, or 'NO PATH' if this is not possible

translation:
### 题面描述

Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 $T$ 个城镇 ( $1 \le T \le 25,000$ )，编号为 $1$ 到 $T$ 。这些城镇之间通过 $R$ 条道路 ( $1 \le R \le 50,000$ ，编号为 $1$ 到 $R$ ) 和 $P$ 条航线 ( $1 \le P \le 50,000$ ，编号为 $1$ 到 $P$ ) 连接。每条道路 $i$ 或者航线 $i$ 连接城镇 $A_i$ ( $1 \le A_i \le T$ )到 $B_i$ ( $1 \le B_i \le T$ )，花费为 $C_i$ 。

对于道路 $0 \le C_i \le 10,000$ ;然而航线的花费很神奇，花费 $C_i$ 可能是负数( $-10,000 \le C_i \le 10,000$ )。道路是双向的，可以从 $A_i$ 到 $B_i$，也可以从 $B_i$ 到 $A_i$ ，花费都是 $C_i$ 。然而航线与之不同，只可以从 $A_i$ 到 $B_i$ 。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台 了一些政策保证：如果有一条航线可以从 $A_i$ 到  $B_i$，那么保证不可能通过一些道路和航线从 $B_i$ 回到 $A_i$ 。由于 $FJ$ 的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇 $S$ ( $1 \le S \le T$) 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

### 输入格式

共 $R+P+1$ 行

第 $1$ 行：四个整数 $T$ , $R$ , $P$ 和 $S$ ，分别表示城镇的数量，道路的数量，航线的数量和中心城镇。

第 $2$ 到 $R+1$ 行：每行三个整数 $A_i$ , $B_i$ 和 $C_i$ ，描述一条道路。

第 $R+2$ 到 $R+P+1$ 行：每行三个整数 $A_i$ , $B_i$ 和 $C_i$ ，描述一条航线。

### 输出格式

共 $T$ 行，第 $i$ 行输出城市 $S$ 到城市 $i$ 的最小花费。如果不能到达，输出`NO PATH`

hint:
6 towns.  There are roads between town 1 and town 2, town 3 and town 4, and town 5 and town 6 with costs 5, 5 and 10; there are planes from town 3 to town 5, from town 4 to town 6, and from town 1 to town 3 with costs -100, - 100 and -10.  FJ is based in town 4.

FJ's cows begin at town 4, and can get to town 3 on the road.  They can get to towns 5 and 6 using planes from towns 3 and 4.  However, there is no way to get to towns 1 and 2, since they cannot go

backwards on the plane from 1 to 3.


title: [USACO11JAN] Profits S

description:
The cows have opened a new business, and Farmer John wants to see how well they are doing. The business has been running for N (1 <= N <= 100,000) days, and every day i the cows recorded their net profit P\_i (-1,000 <= P\_i <= 1,000).

Farmer John wants to find the largest total profit that the cows have made during any consecutive time period. (Note that a consecutive time period can range in length from one day through N days.) Help him by writing a program to calculate the largest sum of consecutive profits.

奶牛们开始了新的生意，它们的主人约翰想知道它们到底能做得多好。这笔生意已经做了N（1≤N≤100,000）天，每天奶牛们都会记录下这一天的利润Pi（-1,000≤Pi≤1,000）。

约翰想要找到奶牛们在连续的时间期间所获得的最大的总利润。（注：连续时间的周期长度范围从第一天到第N天）。

请你写一个计算最大利润的程序来帮助他。

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains a single integer: P\_i

outputFormat: \* Line 1: A single integer representing the value of the maximum sum of profits for any consecutive time period.

hint:
The maximum sum is obtained by taking the sum from the second through the sixth number (4, 9, -2, -5, 8) => 14.

感谢@smartzzh 提供的翻译。


title: [USACO11JAN] Dividing the Gold S

description:
Bessie and Canmuu found a sack of N (1 <= N <= 250) gold coins that they wish to divide as evenly as possible. Coin i has value v\_i (1 <= V\_i <= 2,000). The cows would like to split the pile as evenly as they can, but that is not always possible. What is the smallest difference between the values of the two piles?

In addition, the Bessie and Canmuu have found that there might be multiple ways to split the piles with that minimum difference. They would also like to know the number of ways to split the coins as fairly as possible. If it isn't possible to split the piles evenly, Bessie will get the higher-valued pile.

By way of example, consider a sack of five coins of values: 2, 1, 8, 4, and 16. Bessie and Canmuu split the coins into two piles, one pile with one coin worth 16, and the other pile with the remaining coins worth 1+2+4+8=15. Therefore the difference is 16-15 = 1.  This is the only way for them to split the coins this way, so the number of ways to split it evenly is just 1.

Note that same-valued coins can be switched among the piles to increase the number of ways to perform an optimal split. Thus, the set of coins {1, 1, 1, 1} has six different ways to split into two optimal partitions, each with two coins.

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains a single integer: V\_i

outputFormat:
\* Line 1: A single integer that is the smallest difference of two partitions.

\* Line 2: A single integer that is the number of ways to split the coins with the minimum difference printed in line 1. Since this number can get quite large, print the remainder when divided by 1,000,000.

translation:
Bessie 和 Canmuu 发现了一个有 ***N*** 个金币的袋子(1 <= N <= 250) 。第i个金币有一个价值 ***Vi***
(1 <= Vi <= 2000)他们希望尽可能的把这堆金币平均分配，但有时这是不可能的。找出使两堆价值差最小的分配方案。如果不能完全平均分开，Bessie会获得较高价值那一堆。

举例来说 ： 有一袋5个金币。价值分别是 2,1,8,4,16。
Bessie 和Canmuu把金币分成两堆，第一堆是价值16的金币，另一堆是剩下的1+2+4+8 = 15 个金币，因此，差是1，这是最优分配方案下的唯一分法（即差最小的唯一分法），所以方案数为1。

请你找出 **最小的差值** 以及在这个差值下分配的**方案数。**

输入第一行 N

之后每一行有一个Vi代表第i个金币的价值

输出第一行是最小差值，

第二行是分配方案数 ,由于方案数可能很大，输出***ans mod 1e6***的答案

感谢@ToBiChi 提供翻译


title: [USACO11JAN] Traffic Lights S

background: 征求翻译。如果你能提供翻译或者题意简述，请直接发讨论，感谢你的贡献。

description:
Kenosha, the city nearest Farmer John, has M (1 <= M <= 14,000) roads conveniently numbered 1..M that connect N (2 <= N <= 300) junctions which are conveniently numbered 1..N. No two roads connect the same pair of junctions. No road connects a junction to itself. The integer travel time T\_ij (1 <= T\_ij <= 100) between junctions i and j is the same for both directions (i.e., T\_ij = T\_ji).

Each junction has a single traffic light with two colors: blue or purple. The color of each light alternates periodically: blue for certain duration and then purple for another duration.  Traffic is permitted to commence travel down the road between any two junctions, if and only if the lights at both junctions are the same color at the moment of departing from one junction for the other.  The lights do not necessarily have to be the same on the whole trip down the road.

If a vehicle arrives at a junction just at the moment the lights switch it must consider the new colors of lights. Vehicles are allowed to wait at the junctions. You are given the city map which shows:

```cpp
                                    Init  Remg  Blue   Purple
       4       76         Junction  Color Time  Cycle  Cycle
>>[1B]===[2P]======          1        B    2     16      99
    |   /          \         2        P    6     32      13
  40|  /75          \        3        P    2     87       4
    | /              \       4        P   38     96      49
  [3P]===============[4P]>>
           77
```
```cpp
* The travel times T_ij for all roads
* The durations of the two colors at junction i. (DB_i (1 <= DB_i <= 100) for the blue light and DP_i (1 <= DP_i <= 100) for the purple light)
* The initial color C_i of the light at junction i (a letter 'B' or 'P' with the obvious meaning) and the remaining time R_i (1 <= R_i <= 100) for this color to change
Find the minimum time one needs to get from a given source S (1 <= S <= N) to a given destination D (1 <= D <= N; D != S).
Consider the map below with four junctions and five roads. FJ wants to travel from junction 1 to junction 4. The first light is blue; the rest are purple.
```
The minimum time is 127 utilizing the path 1-2-4.
Initially, the light at junction 1 is blue. Since the light at junction 2 is purple, vehicle waits at junction 1 for 2 seconds then travels 4 seconds to junction 2.

At time 6, the light at junction 2 switches to blue whereas the light at junction 4 has 32 more seconds to switch to blue. However, after 32 seconds, the light at junction 2 switches to purple and the light at junction 4 switches to blue at the same time. So the vehicle needs to wait 13 seconds more for junction 2 to switch to blue then the lights have the same color and vehicle travels 76 seconds to the destination junction 4.

The total time is 2+4+32+13+76=127 seconds.

Below is a more graphical presentation of this travel plan:

```cpp
                                                                                1    1    1    1    1    1
             1    1    2    2    3    3    4    4    5    5    6    6    7    7    8    8    9    9    0    0    1    1    2    2
   0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5....0....5..
   --------------------------------------------------------------------------------------------------------------------------------
J1 BBBPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPBBBBBBBBBBBBBBBBPPPPPPPPPP
J2 PPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
J3 PPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
J4 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
FJ 1..>>>2............................................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>4
```

inputFormat:
\* Line 1: Two space-separated integers: S and D

\* Line 2: Two space-separated integers: N and M

\* Lines 3..N+2: Line i+2 line describes junction i with a character and three integers (all separated by a single space): C\_i, R\_i, DB\_i, and DP\_i

\* Lines N+3..N+M+2: Line N+2+k describes road k with three integers: i, j, and T\_ij

outputFormat: \* Line 1: One integer: the time taken by a minimum-time path from the source junction to the destination junction. If there is no path, output 0.

translation:
## **题目描述**

和FJ靠的最近的城市Kenosha市有 $M$条道路。(编号为$1-M$) 连接着$N$个路口 (编号为$1-N$) 。保证没有重边和自环。

从点$i$到点$j$需要的时间是$T_{ij}$， 且保证$T_{ij}$ = $T_{ji}$

每个路口有一个交通灯，有两种颜色：蓝色和紫色。两个颜色周期性的交替。蓝色持续一定时间，然后紫色持续一定时间。
想要从$i$到$j$只有在$i$和$j$的信号灯颜色相同的时候才可以走(从T1离开i走向j，只需T1时刻i与j的颜色相同即可，无其他任何约束。)

如果在变幻灯的那一秒到$j$，考虑的是变幻后的颜色。
给你所有第$i$个路口的蓝色灯持续时间$DB_i$和紫色灯持续时间$DP_i$
和每个路口刚开始灯的颜色$C_i$,剩余持续时间$R_i$
求一个给定的原点$S$到给定目标点$D$的最小时间。

## 输入输出格式
###   输入格式
 * 第一行两个整数 S和D
 * 第二行两个整数 N和M
 * 第三至N+2行。第i+2行描述点i的信号灯情况 $C_i$,   $R_i$,  $DB_i$,   $DP_i$
 * 第三道N+M+2行：第N+2+k行描述第k条道路 : $i$, $j$, $T_{ij}$
###   输出格式
 * 一个整数代表从S到D最少消耗的时间， 如果S、D不连通，输出0

感谢@ToBiChi 提供翻译


title: [USACO11FEB] Cowlphabet G

description:
Like all bovines, Farmer John's cows speak the peculiar 'Cow'

language. Like so many languages, each word in this language comprises a sequence of upper and lowercase letters (A-Z and a-z).  A word is valid if and only if each ordered pair of adjacent letters in the word is a valid pair.

Farmer John, ever worried that his cows are plotting against him, recently tried to eavesdrop on their conversation. He overheard one word before the cows noticed his presence. The Cow language is spoken so quickly, and its sounds are so strange, that all that Farmer John was able to perceive was the total number of uppercase letters, U (1 <= U <= 250) and the total number of lowercase

letters, L (1 <= L <= 250) in the word.

Farmer John knows all P (1 <= P <= 200) valid ordered pairs of adjacent letters.  He wishes to know how many different valid

words are consistent with his limited data.  However, since

this number may be very large, he only needs the value modulo

97654321.

约翰家的奶牛用别人听不懂的“牛语”联络。牛语采用英文字母，而且区分大小写。牛 语中的语法中，前后字母的衔接非常重要，存在P个基本组合，每个字母之后只能接固定的 几个字母。 约翰担心奶牛正在密谋反对他，于是最近一直在偷听她们的对话。可是牛语太复杂了， 他只模模糊糊地听到了一个单词，并确定了这个单词中有U个大写字母，L个小写字母。约 翰对这个单词很在意，他想知道，有多少牛语词汇拥有U个大写字母，L个小写字母。由于 这个数字太大了，你只要输出答案取 97654321 的余数就可以了。 输入格式 ? ? 第一行：三个用空格隔开的整数：U，L和P，1 ≤ U, L ≤ 250，1 ≤ P ≤ 200 第二行到P + 1行：第i + 1有两个字母Ai和Bi，表示字母Ai后面可以接Bi，没有一对Ai和 Bi是完全相同的

inputFormat:
\* Line 1: Three space-separated integers: U, L and P

\* Lines 2..P+1: Two letters (each of which may be uppercase or lowercase), representing one valid ordered pair of adjacent letters in Cow.

outputFormat: \* Line 1: A single integer, the number of valid words consistent with Farmer  John's data mod 97654321.

hint:
The word Farmer John overheard had 2 uppercase and 2 lowercase letters.  The valid pairs of adjacent letters are AB, ab, BA, ba, Aa, Bb and bB.

The possible words are:

AabB
ABba
abBA
BAab
BbBb
bBAa
bBbB


title: [USACO11FEB] The Lost Cows G

description:
One sunny day farmer John was kidnapped by evil farmer Marcus's cows. FJ wasn't too concerned about his forced holiday but wanted to make sure that his cows got home safely together.

The cows are spread out in every one of FJ's N (3 <= N <= 200) pastures conveniently numbered 1..N. The barn is located at pasture 1. The farm has an interesting navigation system: at every pasture i there are M (1 <= M <= 200) signs S\_ij (1 <= S\_ij <= N) which one could reference as S\_i1..S\_iM; each sign points the way to a pasture. Sometimes a sign points to a path that leads back to the same

pasture.

Farmer Marcus's cows allow FJ to write a single message to all of his cows. FJ's plan is to write a list of sign numbers such that any cow who follows those instructions will all arrive at the barn when each cow has completed all the instructions.

When a cow starts at a given pasture then she will first follow the path indicated by the first sign number on FJ's list. When she arrives at the second pasture, she looks at the second sign of FJ's list and follows the path marked by that sign. She continues until she exhausts the instruction list, at which point she should be at the barn.

Find a list of instructions containing no more than 5,000,000 sign numbers that will guide every cow, from every pasture, to the barn after all instructions are followed.  It is guaranteed that such a list exists.

Consider a set of three signs in four pastures that direct the cows like these do:

```cpp
** Pasture# **
1    2    3    4
Sign 1   4    4    1    3
Sign 2   1    3    2    4
Sign 3   4    2    3    1
```
The set of instructions below will direct cows to the barn from any of the four pastures:

```cpp
Instruction#   Sign#            Instruction#   Sign#
1           1                   5           3
2           2                   6           1
3           1                   7           3
4           2
```
The cow in pasture 1 will read sign #1 at time 1 and be directed to pasture 4.  At time 2, she is in pasture 4 and (per FJ's

instructions) read sign #2 and then be directed to pasture 4. Below is a table that shows the cow's travels:

```cpp
* * * *  Cow in pasture  1  * * * *
Time    CurrentPasture#    WhichSign     Sign->Nextpasture
1            1               1                4
2            4               2                4 (same pasture!)
3            4               1                3
4            3               2                2
5            2               3                2 (same pasture)
6            2               1                4
7            4               3                1 Barn!
```
Similarly: Pasture 2's cow visits pastures [2]-4-4-3-2-2-4-1. Pasture 3's cow visits pastures [3]-1-1-4-4-1-4-1.

Pasture 4's cow visits pastures [4]-3-2-4-4-1-4-1.

Given a set of signs, create a set of instructions.

inputFormat:
\* Line 1: Two space separated integers: N and M

\* Lines 2..M+1: Line i+1 describes the contents of each pasture's N signs with N integers: S\_1i..S\_Ni

outputFormat: \* Lines 1..?: The sign numbers the cows should follow, one per line.

translation:
### 题目描述

给定一张 $n(3\leq n\leq 200)$ 个点的图，每个点都恰好有 $m(1\leq m\leq 200)$ 条出边，第 $i$ 个点的第 $j$ 条出边指向 $a_{i,j}$。

现在这张图上每个点都有一头牛。每次你可以报出一个数 $x(1\leq x\leq m)$，这会使得每一头牛沿着当前所在的点的第 $x$ 条边走一步（即当前在点 $u$ 的牛移动到点 $a_{u,x}$）。

你需要发出不超过 $5\times 10^6$ 条指令，使得在所有的指令执行完后，所有的牛都在编号为 $1$ 的点上。

### 输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行每行 $n$ 个整数，第 $i$ 行的第 $j$ 个整数是 $a_{j,i}$。

### 输出格式

在第 $i$ 行输出你发出的第 $i$ 条指令。


title: [USACO11FEB] Cow Line S

description:
The N (1 <= N <= 20) cows conveniently numbered 1...N are playing yet another one of their crazy games with Farmer John. The cows will arrange themselves in a line and ask Farmer John what their line number is. In return, Farmer John can give them a line number and the cows must rearrange themselves into that line.

A line number is assigned by numbering all the permutations of the line in lexicographic order.

Consider this example:

Farmer John has 5 cows and gives them the line number of 3.

The permutations of the line in ascending lexicographic order: 1st: 1 2 3 4 5

2nd: 1 2 3 5 4

3rd: 1 2 4 3 5

Therefore, the cows will line themselves in the cow line 1 2 4 3 5.

The cows, in return, line themselves in the configuration '1 2 5 3 4' and ask Farmer John what their line number is.

Continuing with the list:

4th : 1 2 4 5 3

5th : 1 2 5 3 4

Farmer John can see the answer here is 5

Farmer John and the cows would like your help to play their game. They have K (1 <= K <= 10,000) queries that they need help with. Query i has two parts: C\_i will be the command, which is either 'P' or 'Q'.

If C\_i is 'P', then the second part of the query will be one integer A\_i (1 <= A\_i <= N!), which is a line number. This is Farmer John challenging the cows to line up in the correct cow line.

If C\_i is 'Q', then the second part of the query will be N distinct integers B\_ij (1 <= B\_ij <= N). This will denote a cow line. These are the cows challenging Farmer John to find their line number.

inputFormat:
\* Line 1: Two space-separated integers: N and K

\* Lines 2..2\*K+1: Line 2\*i and 2\*i+1 will contain a single query.

Line 2\*i will contain just one character: 'Q' if the cows are lining up and asking Farmer John for their line number or 'P' if Farmer John gives the cows a line number.

If the line 2\*i is 'Q', then line 2\*i+1 will contain N space-separated integers B\_ij which represent the cow line. If the line 2\*i is 'P', then line 2\*i+1 will contain a single integer A\_i which is the line number to solve for.

outputFormat:
\* Lines 1..K: Line i will contain the answer to query i.

If line 2\*i of the input was 'Q', then this line will contain a single integer, which is the line number of the cow line in line 2\*i+1.

If line 2\*i of the input was 'P', then this line will contain N space separated integers giving the cow line of the number in line 2\*i+1.

translation:
第一行两个整数 $N,K$。

接下来有 $K$ 组询问，每组询问里先给出 $C_i$，表示操作类型。

如果 $C_i$ 是 `P`，下面给出一个整数 $A_i$，表示求 $1$ 到 $N$ 的第 $A_i$ 个全排列。

如果 $C_i$ 是 `Q`，下面给出 $N$ 个整数 $B_{i,j}$，表示求 $B_{i,1}$ 到 $B_{i,N}$ 这个序列是 $1$ 到 $N$ 的第几个全排列。

对于每个询问，输出相应的答案。

数据范围：$1≤N≤20$，$1≤K≤10^4$，$1≤A_i≤N!$，$1≤B_i≤N$。


title: [USACO11FEB] Best Parenthesis S

description:
Recently, the cows have been competing with strings of balanced parentheses and comparing them with each other to see who has the best one.

Such strings are scored as follows (all strings are balanced): the string '()' has score 1; if 'A' has score s(A) then '(A)' has score 2\*s(A); and if 'A' and 'B' have scores s(A) and s(B), respectively, then 'AB' has score s(A)+s(B). For example, s('(())()') = s('(())')+s('()') = 2\*s('()')+1 = 2\*1+1 = 3.

Bessie wants to beat all of her fellow cows, so she needs to calculate the score of some strings. Given a string of balanced parentheses of length N (2 <= N <= 100,000), help Bessie compute its score.

给定一个只包含左右括号的字符串，得分规则如下：

如果一对括号内没有括号，那么这对括号的得分为1；如果两对括号互不包含（即并列存在），那这两对括号的得分相加；如果括号内包含一对括号，那么这个括号的得分纪为内部括号序列的得分\*2。

例如：对于这样一个字符串："() ()"，两对括号并列存在，则得分为1+1=2;

而对于这样一个字符串："(())"，最外层的括号内层包含一对括号，则得分为2\*1=2.

Bessie想击败所有同事的牛，所以她需要计算某个字符串的评分。给定一个长度为n、只包含括号的字符串（2≤N≤100000），计算其得分帮助Bessie。

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N + 1: Line i+1 will contain 1 integer: 0 if the ith character of the string is '(',  and 1 if the ith character of the string is ')'

outputFormat: \* Line 1: The score of the string. Since this number can get quite large, output the  score modulo 12345678910.

hint:
This corresponds to the string "(())()".

As discussed above.

输出答案要mod12345678910


title: [USACO11FEB] The Triangle S

description:
For her spectacular milk output for the previous month, Farmer John has awarded Bessie a prize -- with a twist.  He has given her a triangular grid with N (1 <= N <= 700) rows (whose lengths vary from 1 through N, of course). Row i of the the grid has i values labeled v\_ij (-1,000,000,000 <= v\_ij <= 1,000,000,000) where j is in the range 1..i.

Bessie chooses a sub-triangle whose side length is at least K (1 <= K <= 20; 1 <= K <= N) within the triangular grid. The sub-triangle is another triangular grid which might be oriented the same as the original triangle or might be 'upside down' with its shorter rows on the bottom instead of the top.

After she chooses her sub-triangle, Farmer John will take the average of all the numbers in the sub-triangle, discarding the digits to the right of the decimal point, and give her that many gold coins (or take that many gold coins from her if the number is negative). Naturally, Bessie would like to maximize her prize (or minimize her loss). Help her solve this problem.

By way of example, Bessie is given this triangular grid with N = 3 rows and must choose a sub-triangle with a side length of at least K = 2. A graphical representation of the triangle is shown below:

```cpp
    / \
   / 5 \
  /-8  4\
 /2 -3  6\
 ---------
```
She could choose any of five valid sub-triangles (one of which is the entire original triangle):

```cpp
                                                   /\
    / \         / \        / \         / \        /5 \
   / 5 \       / \5\      / 5 \       / 5/\      /----\
  /-8  4\     /-8 \4\    /-8  4\     /-8/ 4\    /\-8 4/\
 /2 -3  6\   / 2 -3\6\  /-------\   / 2/-3 6\  / 2\-3/6 \
 ---------   ---------  -2  -3  6   ---------  ----------
  entire      lower        top          lower     upside
 triangle     left                      right      down
```
The one that is lined below is the one with the highest average:

```cpp
    / \
   / 5/\
  /-8/ 4\
 / 2/-3 6\
 ---------
```
The average of this sub-triangle is (4+6-3)/3, which is about

2.3333...; without the fraction, the answer is 2.

Help Bessie calculate the maximum amount of coins which she could receive.

TIME LIMIT: 2 seconds

MEMORY LIMIT: 32 MB

有一个n(1<=n<=700)行的等腰三角形，里面有很多数(-1,000,000,000 <= 数 <= 1,000,000,000)，现在可以选择边长至少为k(1<=k<=20,1<=k<=n)，至多为2k的相似等腰三角形，并且可以倒着选，比如样例可以有这些选择方法：

样例：

```cpp
                                                   /\
    / \         / \        / \         / \        /5 \
   / 5 \       / \5\      / 5 \       / 5/\      /----\
  /-8  4\     /-8 \4\    /-8  4\     /-8/ 4\    /\-8 4/\
 /2 -3  6\   / 2 -3\6\  /-------\   / 2/-3 6\  / 2\-3/6 \
 ---------   ---------  -2  -3  6   ---------  ----------
  entire      lower        top          lower     upside
 triangle     left                      right      down
```
最后问你可以得到的最大平均值为多少（平均值：选出的三角形的累加和div选出个数）

inputFormat:
\* Line 1: Two space-separated integers: N and K

\* Lines 2..N+1: Line i+1 will contain i space-separated integers: v\_ij

outputFormat: \* Line 1: The maximum number of coins that Bessie can receive (or, if negative, the best she can do for her loss).

hint: 感谢 zzkksunboy 提供翻译。


title: [USACO11MAR] Brownie Slicing G

description:
Bessie has baked a rectangular brownie that can be thought of as an RxC grid (1 <= R <= 500; 1 <= C <= 500) of little brownie squares. The square at row i, column j contains N\_ij (0 <= N\_ij <= 4,000) chocolate chips.

Bessie wants to partition the brownie up into A\*B chunks (1 <= A <= R; 1 <= B <= C): one for each of the A\*B cows. The brownie is cut by first making A-1 horizontal cuts (always along integer

coordinates) to divide the brownie into A strips.  Then cut each strip \*independently\* with B-1 vertical cuts, also on integer

boundaries. The other A\*B-1 cows then each choose a brownie piece, leaving the last chunk for Bessie. Being greedy, they leave Bessie the brownie that has the least number of chocolate chips on it.

Determine the maximum number of chocolate chips Bessie can receive, assuming she cuts the brownies optimally.

As an example, consider a 5 row x 4 column brownie with chips

distributed like this:
```
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1
```

Bessie must partition the brownie into 4 horizontal strips, each with two pieces. Bessie can cut the brownie like this:

```
1 2 | 2 1
---------
3 | 1 1 1
---------
2 0 1 | 3
---------
1 1 | 1 1
1 1 | 1 1
```

Thus, when the other greedy cows take their brownie piece, Bessie still gets 3 chocolate chips.

inputFormat:
\* Line 1: Four space-separated integers: R, C, A, and B

\* Lines 2..R+1: Line i+1 contains C space-separated integers: N\_i1, ..., N\_iC

outputFormat: \* Line 1: A single integer: the maximum number of chocolate chips that Bessie guarantee on her brownie

translation:
Bessie 烘焙了一块巧克力蛋糕。这块蛋糕是由 $R\times C(1\leq R,C\leq 500)$ 个小的巧克力蛋糕组成的。第 $i$ 行，第 $j$ 列的蛋糕有 $N_{i,j}(N_{i,j}\leq 4000)$ 块巧克力碎屑。

Bessie 想把蛋糕分成 $A\times B(1\leq A\leq R,1\leq B\leq C)$ 块，给 $A\times B$ 只奶牛。蛋糕先水平地切 $A-1$ 刀（只能切沿整数坐标切）来把蛋糕划分成 $A$ 块。然后再把剩下来的每一块独立地切 $B-1$ 刀，也只能切沿整数坐标切。其他 $A\times B-1$ 只奶牛就每人选一块，留下一块给 Bessie。由于贪心，他们只会留给 Bessie 巧克力碎屑最少的那块。求出 Bessie 最优情况下会获得多少巧克力碎屑。

例如，考虑一个 $5\times4$ 的蛋糕，上面的碎屑分布如下图所示：
```
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1
```
Bessie必须把蛋糕切成4条，每条分成2块。Bessie能像这样切蛋糕:
```
1 2 | 2 1
---------
3 | 1 1 1
---------
2 0 1 | 3
---------
1 1 | 1 1
1 1 | 1 1
```
这样，Bessie至少能获得 $3$ 块巧克力碎屑。


title: [USACO11MAR] Tree Decoration G

description:
Farmer John is decorating his Spring Equinox Tree (like a Christmas tree but popular about three months later). It can be modeled as a rooted mathematical tree with N (1 <= N <= 100,000) elements, labeled 1...N, with element 1 as the root of the tree. Each tree element e > 1 has a parent, P\_e (1 <= P\_e <= N). Element 1 has no parent (denoted '-1' in the input), of course, because it is the root of the tree.

Each element i has a corresponding subtree (potentially of size 1) rooted there. FJ would like to make sure that the subtree corresponding to element i has a total of at least C\_i (0 <= C\_i <= 10,000,000) ornaments scattered among its members. He would also like to minimize the total amount of time it takes him to place all the ornaments (it takes time K\*T\_i to place K ornaments at element i (1 <= T\_i <= 100)).

Help FJ determine the minimum amount of time it takes to place ornaments that satisfy the constraints.  Note that this answer might not fit into a 32-bit integer, but it will fit into a signed 64-bit integer.

For example, consider the tree below where nodes located higher on the display are parents of connected lower nodes (1 is the root):

```cpp
For example, consider the tree below where nodes located higher on
the display are parents of connected lower nodes (1 is the root):

               1
               |
               2
               |
               5
              / \
             4   3

Suppose that FJ has the following subtree constraints:

                  Minimum ornaments the subtree requires
                    |     Time to install an ornament
       Subtree      |       |
        root   |   C_i  |  T_i
       --------+--------+-------
          1    |    9   |   3
          2    |    2   |   2
          3    |    3   |   2
          4    |    1   |   4
          5    |    3   |   3

Then FJ can place all the ornaments as shown below, for a total
cost of 20:

            1 [0/9(0)]     legend: element# [ornaments here/
            |                      total ornaments in subtree(node install time)]
            2 [3/9(6)]
            |
            5 [0/6(0)]
           / \
 [1/1(4)] 4   3 [5/5(10)]
```

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains three space-separated integers: P\_i, C\_i, and T\_i

outputFormat:
\* Line 1: A single integer: The minimum time to place all the

ornaments

translation:
给定一颗以 $1$ 为根的有根树，第 $i$ 个结点的父结点为 $P_i$（$P_1=-1$），在第 $i$ 个结点上挂一个装饰物的代价为 $T_i$，每个结点可以挂任意个。现在给定每棵树子树中至少挂的装饰物个数 $C_i$，求满足要求的最少花费。

$1 \leq n \leq 10^5$，$1 \leq T_i \leq 100$，$1 \leq C_i \leq 10^7$，请注意要开 long long。

### 输入格式

第一行一个整数 $n$。

第 $1$ 行至第 $n$ 行，在第 $i+1$ 行有三个整数，分别表示 $P_i$，$C_i$ 和 $T_i$。

### 输出格式

一行一个整数表示最小花费。

### 样例解释
```
样例中给出的树如下：
               1
               |
               2
               |
               5
              / \
             4   3

给定如下数据：

                  该子树中所需的装饰物个数
                    |     在该节点挂一个装饰物的花费
                    |       |
       结点编号 |   C_i  |  T_i
       --------+--------+-------
          1    |    9   |   3
          2    |    2   |   2
          3    |    3   |   2
          4    |    1   |   4
          5    |    3   |   3

最佳方案如下：

            1 [0/9(0)]
            |
            2 [3/9(6)]
            |
            5 [0/6(0)]
           / \
 [1/1(4)] 4   3 [5/5(10)]

（格式：[在此处挂的装饰物个数/子树中装饰物总数(在此结点花费代价)]）
```


title: [USACO11MAR] Meeting Place S

description:
Bessie and Jonell are great friends. Since Farmer John scrambles where the cows graze every day, they are sometimes quite far from each other and can't talk.

The pastures and paths on FJ's farm form a 'tree' structure.  Each pasture has exactly one distinct path to any other pasture, and each pasture (except pasture #1, the 'root') also has a single parent node.

Bessie and Jonell have decided that they will always meet at the closest pasture that that is both an ancestor of Jonell's pasture and of Bessie's pasture.

FJ created a map of his N (1 <= N <= 1,000) pastures (conveniently numbered 1..N) that tells the parent P\_i (1 <= P\_i <= N) of each pasture except pasture 1, which has no parent.

FJ has released his daily grazing schedule for the next M (1 <= M <= 1,000) days, so Bessie and Jonell are deciding where they should meet each day for gossip. On day k, Bessie is in pasture B\_k (1 <= B\_k <= N) and Jonell is in pasture J\_k (1 <= J\_k <= N).

Given a map and schedule, help Bessie and Jonell find their meeting places.

```cpp
Consider, for example, the following farm layout:

                            Pasture      Parent Pasture
             [1]           ---------    ----------------
            / | \              1              ---
           /  |  \             2               1
         [2] [3] [6]           3               1
         /        | \          4               2
        /         |  \         5               8
      [4]        [8]  [9]      6               1
                /   \          7               8
               /     \         8               6
             [5]     [7]       9               6

Here are the meeting places that Bessie and Jonell would choose
given a six day schedule of their initial grazing locations:

              Bessie      Jonell       Meeting Place
             --------    --------     ---------------
                 2           7               1
                 4           2               2
                 1           1               1
                 4           1               1
                 7           5               8
                 9           5               6
```

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..N: Line i contains a single integer that describes the parent of pasture i:  P\_i

\* Lines N+1..N+M: Line k+N describes Bessie and Jonell's respective pastures with two space-separated integers: B\_k and J\_k

outputFormat: \* Lines 1..M: Line j contains the meeting place Bessie and Jonell would use for line j+N of the input

translation:
农场是由N（1≤N≤1000）个节点组成的一棵树，1是树的根。有两头奶牛分别在两个节点，他们有M（1≤M≤1000）天要见面，见面地点在她们所在两个节点的路径上离根节点最近的节点。求出每天她们见面的节点编号。
输入：第一行两个整数N, M，接下来N-1行（这里的 i 是从 2 ~ n），第i行表示第i个节点的父亲编号，接下来M行每行两个整数表示当天两头奶牛所在的节点编号。
输出：输出M行，回答每个询问。

感谢@x咫尺天涯x 提供的翻译和ROY1994 提供的建议


title: [USACO11MAR] Package Delivery S

description:
Farmer John must deliver a package to Farmer Dan, and is preparing to make his journey. To keep the peace, he gives a tasty treat to every cow that he meets along his way and, of course, FJ is so frugal that he would like to encounter as few cows as possible.

农夫约翰必须送一个包裹给农夫丹，并准备去旅行。为了保持和平，他必须给每一头遇到的奶牛一些吃的，当然，FJ很节俭，他想可能遇到尽可能少的奶牛。

FJ has plotted a map of N (1 <= N <= 50,000) barns, connected by M (1 <= M <= 50,000) bi-directional cow paths, each with C\_i (0 <= C\_i <= 1,000) cows ambling along it. A cow path connects two distinct barns, A\_i and B\_i (1 <= A\_i <= N; 1 <= B\_i <= N; A\_i != B\_i). Two barns may be directly connected by more than one path. He is currently located at barn 1, and Farmer Dan is located at barn N.

FJ 已经绘制了 $N(1 \le N \le 50000)$ 个谷仓的地图，通过 $M(1 \le M \le 50000)$ 条双向牛道，每条双向牛道上有 $c[i](0 \le c[i] \le 1000)$ 奶牛漫步。双向牛道连接两个不同的谷仓，$a[i]$ 和 $b[i](1 \le a[i] \le N,1 \le b[i] \le N, a[i] \neq b[i])$。两个谷仓可以由一条以上的小路直接连接。他目前在 $1$ 号谷仓，农夫丹位于 $N$ 号谷仓。

Consider the following map:

```cpp
           [2]---
          / |    \
         /1 |     \ 6
        /   |      \
     [1]   0|    --[3]
        \   |   /     \2
        4\  |  /4      [6]
          \ | /       /1
           [4]-----[5]
                3
```
The best path for Farmer John to take is to go from 1 -> 2 -> 4 -> 5 -> 6, because it will cost him 1 + 0 + 3 + 1 = 5 treats.

Given FJ's map, what is the minimal number of treats that he should bring with him, given that he will feed each distinct cow he meets exactly one treat? He does not care about the length of his journey.

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..M+1: Three space-separated integers: A\_i, B\_i, and C\_i

outputFormat: \* Line 1: The minimum number of treats that FJ must bring


title: [USACO11MAR] Bovine Bridge Battle S

background: 给定N（4 <= N <= 1,000）个整点的坐标 (-1,000,000,000 <= X\_i <= 1,000,000,000; -1,000,000,000 <= Y\_i <= 1,000,000,000，X\_i，Y\_i∈Z)，求card{{(X\_a,Y\_a),(X\_b,Y\_b),(X\_c,Y\_c),(X\_d,Y\_d)}|四点呈中心对称}

description:
Each of Farmer John's N (4 <= N <= 1,000) cows is patiently waiting in the main pasture with cow i at point with integer coordinates (X\_i, Y\_i) (-1,000,000,000 <= X\_i <= 1,000,000,000; -1,000,000,000 <= Y\_i <= 1,000,000,000).

The cows wish to form into groups of four in order to play Bridge, their new favorite card game. Each group must satisfy an important constraint: four cows are allowed to team up if and only if there exists some point X somewhere in the plane (and not coincident with any of the four points of the potential group of four) such that rotating any of the group's cows 180 degrees about that point X gives the position of some other cow in the group.

Please help the cows determine the number of sets of four cows that can form a Bridge group.

By way of example, suppose eight cows are standing at eight points:

|
f\*
```cpp
|             a = (-3, 1)    e = (-1, 1)
b*     |             b = (-2, 2)    f = ( 0, 3)
a      e  |             c = (-3, 0)    g = ( 2, 0)
*     *  |             d = (-2, 0)    h = ( 3, 0)
```
c  d     |     g  h
---------\*--\*-----+-----\*--\*---------

|
Then the three legal sets of four cows are {a, b, e, d} (they rotate around point (-2, 1)), {b, c, e, f} (around the point (-1.5, 1.5)), and {c, d, g, h} (around (0,0)).

The supplied locations of the cows given are all distinct, although they are supplied in no particular order. Furthermore, the answer will fit into a signed 32-bit integer.

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains two space-separated integers: X\_i and Y\_i

outputFormat: \* Line 1: A single integer that is the number of sets of 4 cows that form valid groups for bridge.

translation:
农场主约翰有 $N$ 头牛，牛 $i$ 位于整数坐标点 $(X_i,Y_i)$。

奶牛们希望每四头牛分成一组，玩他们最喜欢的纸牌游戏“桥牌”。

每组必须满足一个重要的约束条件：

当且仅当平面中存在点 $X$ 时（一组的四个点允许重合，并且 $X$ 不与可能的组中的四个点中的任何一个相重合），使得组中的四个点呈中心对称。

请帮助奶牛确定可以组成一个桥群的四头奶牛的数量。

举个例子，假设八头牛站在八个点上：

$a=(-3,1),b=(-2,2),c=(-3,0),d=(-2,0),e=(-1,1),f=(0,3),g=(2,0),h=(3,0)$

四头牛的三个合法集合是：

{$a,b,e,d$}，关于 $ (-2，1)$ 对称，

{$b,c,e,f$}，关于 $(-1.5，1.5)$ 对称，

{$c,d,g,h$}，关于 $(0,0)$ 对称。

$4\le N\le 10^3$，$-10^8\le X_i,Y_i\le 10^8$，$X_i,Y_i\in Z$。


title: [USACO11OPEN] Odd degrees G

description:
The cows are being invaded! Their republic comprises N (1 <= N <= 50,000) towns that are connected by M (1 <= M <= 100,000) undirected paths between two towns A\_i and B\_i (1 <= A\_i <= N; 1 <= B\_i <= N; A\_i != B\_i; no duplicate paths will occur). However the republic is not necessarily connected--there may be pairs of towns that are unable to reach each other through the paths.

The cows know their invaders plan to conduct an inventory of every path within their republic, so they are willing to shut down various paths to make it as difficult as possible for their invaders to do so.

Please help the cows find a way to shut down a subset of the paths such that each town has an odd number of remaining paths connected to it, or determine if no such subset exists.

For example, consider the following cow republic:

1---2
\ /
3---4
If we keep the paths 1-3, 2-3, and 3-4, and remove the path 1-2, then towns 1, 2, and 4 will be an endpoint of exactly one path, whereas town 3 will be an endpoint of three paths:

1   2
\ /
3---4

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..M+1: Line i+1 contains two space-separated integers: A\_i and B\_i

outputFormat:
\* Line 1: A single integer that is the number of paths to keep. If no subset exists output only a single line with the integer -1.

\* Lines 2..K+1: Each line contains an index of an path to keep, in the range 1..M. These indices must be pairwise distinct.

translation:
## 题意
牛们正在被入侵。 有$N$个点，由$M$条无向边连接。 无向边从$A_i$到$B_i$。数据保证无重边，但不保证连通(即从一个点不一定能到达另一点)。

牛知道入侵他们的人正计划清点所有的边，所以他们想切掉一些边使入侵者的计划尽可能的困难

请找出一个方法，留下一些边，使每个点都只有奇数条边与之连接。并输出留下的边的方案。

下面是一个样例
```
1---2
 \ /
  3---4
我们把1——2那条边拆掉， 就会变成下图
1   2
 \ /
  3---4
对于每个点都只有奇数条边连接，符合题意
```
## 读入输出格式
 ### 读入格式
 * 第一行两个整数 $N$ 和 $M$
 * 第二到$M+1$行，每行描述一条边 有两个整数$A_i$和$B_i$
 ### 输出格式
 * 第一行一个整数 剩下边的数量，如果不可能请输出-1
 * 之后每一行一个数，边的编号(按输入顺序来)。

感谢@ToBiChi 提供翻译

hint: 感谢@cn：苏卿念 提供的Special Judge


title: [USACO11OPEN] Soldering G

description:
The cows are playing with wires! They have learned a technique called soldering, in which they connect two pieces of wire together by attaching the endpoint of one wire to a location along the length of the other. (Soldering endpoint to endpoint is not allowed.) There can be multiple solder junctions at the same point.

The cows have a plan for an Amazing Structure they would like to build. It is in the form of a graph with N (1 <= N <= 50,000) nodes and N-1 edges of unit length so that each pair of nodes is connected. Each edge is described by a pair of integers, A and B (1 <= A <= N; 1 <= B <= N; A != B).

The cows are able to buy wire from a local store; however longer wire is more expensive. In particular the cows can buy a wire of length L with cost L\*L, but they cannot cut wires or join wires together.

Given the plan, the cows would like solder wires together to build their Amazing Structure. Please help them find the minimum possible cost!

Test data worth at least 50% of the points will have N <= 2,000.

Partial feedback will be provided on your first 50 submissions to this problem.

TIME LIMIT: 2 seconds

MEMORY LIMIT: 64 MB

奶牛决定用电线焊接出一个特殊图形，这个图形是连通的，由N个点，N -1条边组成， 每条边的长度都是1。焊接所用的电线要从当地的商店里买。越长的电线越贵，一条长度为 L的电线售价为L^2 。 奶牛们已经学会了基本的焊接方法， 她们会把某条电线的一个端点焊接到另一条电线的 中间某个位置， 但她们没有学会如何把两条电线的端点直接焊接起来， 也没有学会怎么把电 线剪断。 告诉你奶牛准备焊接的图形，请告诉奶牛怎么焊接才能最节约材料费用。

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N: Two space-separated integers describing an edge: A and B

outputFormat: \* Line 1: A single integer, the cost of soldering the tree together. Note that this number may not always fit in a 32-bit integer.

hint: Since all nodes in the structure are connected to node 1, we only need to buy one wire of length 2 and three of length 1, for a total cost of 2 \* 2 + 1 \* 1 + 1 \* 1 + 1 \* 1 = 7.


title: [USACO11OPEN] Cow Checkers S

description:
One day, Bessie decides to challenge Farmer John to a game of 'Cow Checkers'. The game is played on an M\*N (1 <= M <= 1,000,000; 1 <= N <= 1,000,000) checkerboard that initially contains a single checker piece on the checkboard square coordinates (X, Y) (0 <= X < M; 0 <= Y < N). The bottom leftmost square of the checkerboard has

coordinates (0, 0), and the top rightmost square has coordinates (M-1, N-1). Bessie always moves first, and then the two players alternate turns.  Each turn comprises one of three types of moves:

1) Move the checker piece to any square on the same row to the left of its current position.

2) Move the checker piece to any square on the same column below its current position.

3) Move the checker piece to any spot k squares below and k squares to the left of the current square (where k is any positive integer such that this new spot is still on the checkerboard).

The first player unable to make a move (i.e., because the checker is at (0, 0)) loses. Given that Bessie always goes first, determine who will win the game if both play optimally.

Play and report the winner for T games (1 <= T <= 1,000) reading in a new X,Y starting value for each new game.

有一天，Bessie准备玩一个叫做奶牛跳棋的游戏，来挑战Farmer John。

这个游戏的棋盘大小为 M\*N (1 <= M <= 1,000,000; 1 <= N <= 1,000,000) 。最初棋盘上只有一个棋子在（x,y），棋盘的左下角坐标是（0,0），右上角的坐标是（M-1，N-1）。

每次游戏Bessie都是第一个开始，之后两个人轮流。

每次下棋的时候都有三种走法：

1.向左走任意步

2.向下走任意步

3.向左走k步然后向下走k步（k可随便取值，只要不走出棋盘）

首先走到（0,0）的人为胜利者。

游戏共有T次，每次都会给出一个新的坐标（x,y），请输出每一轮赢家的名字。

inputFormat:
\* Line 1: Two space-separated integers: M and N

\* Line 2: A single integer: T

\* Lines 3..T+2: Two space-separated integers: X and Y

第一行：M N

第二行：T

第三行到第T+2行:这一轮的X Y

outputFormat:
\* Lines 1..T: Should contain either 'Farmer John' or 'Bessie' depending on who wins each  game.

共T行，每一行输出那一轮的赢家

hint:
Farmer John and Bessie are playing one game on a 3\*3 checkerboard with the checker piece initially at (1, 1) (i.e. at the center of the board).

Bessie initially can only move the checker piece to either (1, 0) or (0, 1), or (0, 0). Bessie can immediately win by moving the piece to (0, 0).

起点在（1,1），一开始有三种选择（1,0）,（0,1），（0,0）只要Bessie在开始时将棋子移到（1,0）或（0,1），就必胜无疑。

感谢@ 2014nhc  提供的翻译


title: [USACO11OPEN] Forgotten Password S

description:
As has happened to so many of us, Bessie has forgotten her cowtube password. She does, however, remember some handy bits of information about it.

First, she remembers that her password (denoted as variable P) has length L (1 <= L <= 1,000) roman characters and can be split into one or more words (not necessarily unique) from a dictionary composed of NW (1 <= NW <= 1,000) unique words.  A word W\_i is defined as a sequence of 1..20 lowercase letters of the Roman alphabet ('a'..'z').

She also remembers certain letters from her password along with their positions.

Consider the following example. Bessie knows that her password looks like 'a??l?ban???????' ('?' represents a letter she cannot remember), and her dictionary has the following words:

apple
cow
farmer
banana
bananas

pies
The two possible passwords for Bessie to have are 'applebananapies' and 'applebananascow'.

Given the dictionary, and the letters that Bessie remembers, please find her password. If more than one password is valid, find the lexicographically least string that works.

就像在我们身上发生很多次的情况一样，Bessie又一次忘记了她的牛场管理员密码，她只能记得密码的一部分。

首先，她记得她的密码是长度为L（1<=L<=1000）的字符串，并且她的密码中出现过的所有单词都记录在她有NW个单词的字典中，字典中的单词Wi是由1-20个字母组成的单词。

她只记得她的密码中的一部分字母和它的位置。例如，Bessie记得她的密码为“a??l?ban???????”（其中，？是她不能记得的字母），她的字典中有在她密码中出现的所有单词“apple cow farmer banana bananas pies”，但是注意，字典中的单词可以不再密码中出现但密码中的单词一定在字典中。所以，Bessie的密码的两种可能是“applebananapies”和“applebananascow”，因为前一种字典序较前，故输出“applebananapies”。

现在，给你Bessie记得的字母和她的字典，求她的管理员密码。如果有多个答案，则输出字典序较小的那一个。

inputFormat:
\* Line 1: Two space-separated integers: L and NW

\* Line 2: A string of length L: P

\* Lines 3..NW+2: Line i+2 contains the ith word in the dictionary: W\_i

· 第一行：她密码的长度L和单词数量NW，用一个空格隔开

· 第二行：她所记得的密码字符串，没有多余空格

· 第三行到第NW+2行：单词Wi，一行一个单词

outputFormat:
\* Line 1: The lexicographically least password that fits

一行：Bessie的密码，不要有多余空格。

samples:
15 6
a??l?ban???????
apple
cow
farmer
banana
bananas
pies

hint: 感谢@JJYZ\_cbh 提供翻译


title: [USACO11OPEN] Learning Languages S

description:
Farmer John's N (2 <= N <= 10,000) cows, conveniently numbered 1..N, are fluent in some M (1 <= M <= 30,000) languages, also conveniently numbered from 1..M. Cow i can speak in K\_i (1 <= K\_i <= M) languages, namely L\_i1, L\_i2,..., L\_{iK\_i} (1 <= L\_ij <= M). FJ's cows aren't THAT smart, so the sum of K\_i over all cows i is at most 100,000.

Two cows can't directly talk to each other unless both speak a common language. However, cows can pass messages along, translating if necessary. In other words, cows A and B can have a conversation if and only if there exists a sequence of cows T\_1, T\_2, ..., T\_k such that A and T\_1 share a language, T\_1 and T\_2 share a language, etc., and T\_k and B share a language.

Farmer John wishes that his cows could be even more social, so he wants all his cows to be able to socialize with any other cow. He can buy books to teach any one of his cows any language he pleases. Being a fairly frugal farmer, FJ wants to purchase the minimum number of books necessary to enable all of his cows to speak to each other. Help him determine:

\* The minimum number of books he must purchase

\* Any set of books assigned to cows in any order which will help him meet this goal; a program will grade your output.

By way of example, suppose there are three cows named Alberta, Bessie, and Contessa along with three languages denoted as #1, #2, and #3. Alberta can speak languages #2 and #3, Bessie can speak language #2, and Contessa can speak language #1. Currently, Alberta and Bessie can talk to each other, but Contessa is left alone.

```
#1   #2   #3
Alberta           x    x
Bessie            x
Contessa     x
```
FJ wants to fix this situation, so he can buy Contessa a book to teach her language #2. This will ensure all cows speak the same language, so they can all communicate with one another.

Note that an alternate solution exists: instead, FJ could buy

Contessa a book to teach her language #3. Not all cows would speak the same language, but this would still be a valid solution because Contessa could communicate through Alberta (who also speaks language #3) if she wants to talk to Bessie. Other alternatives exist, and any valid alternate solution will also be accepted.

农夫约翰的$N(2<=N<=10,000)$只奶牛标号为$1..N$，同样的有$M(1<=M<=30,000)$种牛语标号为$1..M$，第i只奶牛会说$K_i(1<=K_i<=M)$种牛语，分别为$L_i1,L_i2,…,L_{iK_i}(1<=L_ij<=M)$，农夫的奶牛不是特别聪明，所以$K_i$的累加和不大于$100,000$。

两只奶牛只有当他们至少有一门语言一样的时候才可以沟通。否则这两只奶牛就需要别人来帮他们翻译才能交流。换句话说，A和B要进行沟通，他们可以通过$T_1,T_2,…,T_k$来传递，比如A和$T_1,T_1$和$T_2,…,T_k$和B进行交流。

农夫希望他的奶牛可以多多沟通，所以他买了很多课本去教她的奶牛语言。当然农夫非常的吝啬，他希望买最少的书就可以让所有的奶牛可以交流。你的任务就是帮他算出最少需要买几本书。

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..N+1: Line i+1 describes the languages that cow i can speak with $(K_i)+1$ space-separated integers: $K_i$, $L_i1$,

L\_i2,...,L\_i{K\_i}.

outputFormat:
\* Line 1: A single integer that is the minimum number of books that FJ must purchase.

\* Lines 2..B+1: Line i+1 contains two space-separated integers: the language id # and the id # of the cow to receive book i. If multiple solutions exist, print any one.


title: [USACO10OCT] Making Money G

background:
FJ又经营起了古董生意，买卖一些像奶牛圣诞树上的装饰之类的小玩意。他知道他会将他能存储的N(1<=N<=100)件不同的奶牛古董每件都卖出。

而且如果他的钱足够多他可以买他想要的任意数量的古董（即他可以购买的古董数量没有限制）。他只有M(1<=M<=100,000)元钱来买古董，但他想要在他经商的第一年年末最大化他的利润（这有点难以解释）。

第i种古董采购需要花费Ci(1<=Ci<=100,000)元钱，每卖掉一件可以获得Ri(1<=Ri<=100,000)元钱(每卖一件的利润为Ri-Ci)。FJ可以以任意顺序卖出他的货物。他并不需要花光他所有的钱来购买古董。

FJ在他经商的第一年年末能得到的最大总利润（利润=初始钱数-总花费+总收入）是多少呢？输入数据保证这个数字不会超过1,000,000,000.

假设FJ只有3种古董而且开始时有M=17元钱。下面是三种古董的花费和收入。

古董 花费 收入

1 2 4

2 5 6

3 3 7

在这种情况下，FJ应该花15元购买5个3号古董，再花2元购买1个1号古董，总共17元。他的利润是5\*(7-3)+1\*(4-2)=5\*4+1\*2=22元。他不能获得比这更多的利润了。

提示：第二个样例很有挑战性，但我们的答案是正确的。

输入格式：

第1行：两个以空格分开的整数：N和M

第2行到第N+1行：第i+1行包括两个以空格分开的整数：Ci和Ri

输出格式

第1行：FJ能获得的最大利润

description:
FJ has gone into the curio business, buying and selling knickknacks like cow Christmas tree ornaments. He knows he will sell every single curio he can stock from a catalog of N (1 <= N <= 100)

different cow curios, and he can buy as many of each kind of curio as his heart desires. He has only M (1 <= M <= 100,000) money to invest but wants to maximize his profit (which has a slightly unusual definition) at the end of his first year in business.

Curio type i costs C\_i (1 <= C\_i <= 100,000) money to purchase and yields R\_i (1 <= R\_i <= 100,000) revenue for each curio sold (a profit of R\_i-C\_i). FJ can mix and match the curios he sells in any way he wishes. He need not spend all his money when purchasing curios.

What is the greatest amount of total profit (profit = initial\_cash - all\_costs + all\_sales) FJ can have at the end of his first year? This number is guaranteed to be less than 1,000,000,000.

Consider the situation when FJ has just 3 kinds of curios and starts with M=17. Below are the cost and revenue numbers for each curio:

Curio     Cost     Revenue

#        C\_i       R\_i

1         2         4

2         5         6

3         3         7

In this case, FJ should purchase 5 curios of type 3 for 15 money and 1 more curio of type 1 for 2 money, a total of 17 money. His profit will be 5 \* (7-3) + 1 \* (4-2) = 5\*4 + 1\*2 = 22 money. He can do no better than this given the cost and revenue structure.

NOTE: The second test case is challenging -- but our answer is correct.

inputFormat:
\* Line 1: Two space-separated integers: N and M

\* Lines 2..N+1: Line i+1 contains two space-separated integers: C\_i and R\_i

outputFormat: \* Line 1: The maximum profit FJ can generate given the costs and revenues


title: [USACO10OCT] Soda Machine G

description:
To meet the ever-growing demands of his N (1 &lt;= N &lt;= 50,000) cows, Farmer John has bought them a new soda machine. He wants to figure out the perfect place to install the machine.

The field in which the cows graze can be represented as a one-dimensional number line. Cow i grazes in the range A\_i..B\_i (1 &lt;= A\_i &lt;= B\_i; A\_i &lt;= B\_i &lt;= 1,000,000,000) (a range that includes its endpoints), and FJ can place the soda machine at any integer point in the range 1..1,000,000,000.  Since cows are extremely lazy and try to move as little as possible, each cow would like to have the soda machine installed within her grazing range.

Sadly, it is not always possible to satisfy every cow's desires. Thus FJ would like to know the largest number of cows that can be satisfied.

To demonstrate the issue, consider four cows with grazing ranges 3..5, 4..8, 1..2, and 5..10; below is a schematic of their grazing ranges:

```cpp

         1   2   3   4   5   6   7   8   9  10  11  12  13
         |---|---|---|---|---|---|---|---|---|---|---|---|-...
                 aaaaaaaaa
                     bbbbbbbbbbbbbbbbb
         ccccc           ddddddddddddddddddddd
```
As can be seen, the first, second and fourth cows share the point 5, but the third cow's grazing range is disjoint.  Thus, a maximum of 3 cows can have the soda machine within their grazing range.

有N个人要去膜拜JZ，他们不知道JZ会出现在哪里，因此每个人有一个活动范围，只要JZ出现在这个范围内就能被膜拜，

伟大的JZ当然希望膜拜他的人越多越好，但是JZ不能分身，因此只能选择一个位置出现，他最多可以被多少人膜拜呢，

这个简单的问题JZ当然交给你了

inputFormat:
\* Line 1: A single integer: N

\* Lines 2..N+1: Line i+1 contains two space-separated integers: A\_i and B\_i

outputFormat: \* Line 1: A single integer representing the largest number of cows whose grazing intervals can all contain the soda machine.

translation:
**为了满足fj所有的N(1<=n<=50000)头奶牛的需求，fj新买了一台汽水机。他想找到一个最完美的位置来安放它。**

**奶牛的牧场可以被表示为一个一维数轴，第i个奶牛被放牧的区间是[Ai...Bi]（包含端点），fj可以把汽水机放在[1..1,000,000,000]。**

**因为奶牛们都懒得要死，她们想尽可能的少移动。她们希望汽水机被放在自己的放牧区间内。**

**遗憾的是，fj并不总能满足所有奶牛的要求，所以他想请你帮忙算出他能满足的奶牛数目**

hint: If the soda machine is placed at location 5, cows 1, 2, and 4 can be satisfied. It is impossible to satisfy all four cows.


title: [USACO11NOV] Cow Lineup S

description:
Farmer John has hired a professional photographer to take a picture of some of his cows.  Since FJ's cows represent a variety of different breeds, he would like the photo to contain at least one cow from each distinct breed present in his herd.

FJ's N cows are all standing at various positions along a line, each described by an integer position (i.e., its x coordinate) as well as an integer breed ID.  FJ plans to take a photograph of a contiguous range of cows along the line.  The cost of this photograph is equal its size -- that is, the difference between the maximum and minimum x coordinates of the cows in the range of the photograph.

Please help FJ by computing the minimum cost of a photograph in which there is at least one cow of each distinct breed appearing in FJ's herd.

inputFormat:
\* Line 1: The number of cows, N (1 <= N <= 50,000).

\* Lines 2..1+N: Each line contains two space-separated positive integers specifying the x coordinate and breed ID of a single cow.  Both numbers are at most 1 billion.

outputFormat: \* Line 1: The smallest cost of a photograph containing each distinct breed ID.

translation:
### 问题描述

农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种，他喜欢他的照片包含每

个品种的至少一头牛。

约翰的牛都站在一条沿线的不同地方， 每一头牛由一个整数位置 $X_i$ 以及整数品种编号 $ID_i$ 表示。

约翰想拍一张照片，这照片由沿线的奶牛的连续范围组成。照片的成本与规模相当，这就意味着，在一

系列照片中的最大和最小 $X$ 坐标的差距决定了照片的成本。

请帮助约翰计算最小的照片成本，这些照片中有每个不同的品种的至少一头牛，没有两头牛愿意站

在同一个地点的。

### 输入格式

第 $1$ 行：牛的数量 $N$；

第 $2..1+N$ 行：每行包含 2 个以空格分隔的正整数 $X_i$ 和 $ID_i$；意义如题目描述；

### 输出格式

输出共一行，包含每个不同品种 $\rm ID$ 的照片的最低成本。

hint:
There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1.

The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd.