title: [POI2006] MAG-Warehouse

description:
The streets of the New Byte City form a rectangular grid - those running east-west are simply called streets, while those running north-south are called avenues. To avoid mistakes, we shall call them h-streets and v-streets, respectively. The v-streets are numbered from $1$ to $500\ 000\ 000$ eastwards. Similarly, the h-streets are numbered from $1$ to $500\ 000\ 000$ northwards. Every v-street crosses every h-street and, conversely, every h-street crosses every v-street. The distance between two consecutive v-streets, as well as between two consecutive h-streets, is exactly one kilometre.

 ![](https://cdn.luogu.com.cn/upload/pic/6964.png)

There are $k$ shops in the city, each one of them is situated at a crossroads. Byteasar, the merchant, supplies every single one of the $k$ shops, and furthermore he returns to some of them several times a day with fresh supplies. Recently he has decided to have a warehouse built, from which the goods would be delivered. For obvious reasons, it should stand at a crossroads. The lorry loaded with goods can supply only one shop per course - it leaves the warehouse, delivers to the shop and returns to the warehouse. The lorry always picks the shortest path from the warehouse to the shop, and the shortest one back (possibly the same one). The distance between points $(x_i, y_i)$ and $(x_j, y_j)$ equals $\max \{ |x_i - x_j|, |y_i - y_j| \}$.

TaskWrite a programme that:

reads the locations of shops, as well as the numbers of their daily deliveries, from the standard inputdetermines such a warehouse's position that the summary distance of the lorry's daily route is minimal,writes the result to the standard output.

给定一个网格图，其上有一堆坏点(整点，同一位置多个)，求一个整点，使得该整点到所有的坏点的**切比雪夫距离**之和最小。

求这个整点位置。(横纵坐标最大)

inputFormat:
The first line of the standard input contains one integer $n$ ($1 \le n \le 100\ 000$), the number of shops in the New Byte City.

The following $n$ lines contain the shops' descriptions. The $(i+1)$'th line contains three integers $x_i$, $y_i$ and $t_i$ ($1 \le x_i, y_i \le 500\ 000\ 000$, $1 \le t_i \le 1\ 000\ 000$), separated by single spaces. This triple means that the $i$'th shop lies at the crossing of $x_i$'th v-street and $y_i$'th h-street and the lorry delivers goods to this shop $t_i$ times a day.

outputFormat: The first and only line of the standard output should contain two integers $x_m$ and $y_m$, separated by a single space, denoting the optimal position of the warehouse as the crossroads of the $x_m$'th v-street and the $y_m$'th h-street. Should there be many optimal solutions, your programme is to pick one of them arbitrarily.

hint: 感谢@oscar 提供SPJ


title: [POI2006] SZK-Schools

type: P

description:
B 国境内有 $n$ 所学校，每所学校都有一个 $1 \sim n$ 的编号。

由于管理过于宽松，可能存在两个学校同时用一个编号的情况，当然也存在一个编号没有学校用的情况。

现在国王决定重新给所有学校编号，使得任意两个学校的编号不同。

当然，改变编号是一个很繁重的工作，学校不希望自己的编号改变太多。每个学校都有一个可以接受的新编号区间 $[a,b]$，以及改变编号的单位成本 $k$。如果一个学校的旧编号为 $m$，新编号为 $m'$，那么给这个学校改变编号的成本即为 $k \times |m'-m|$。

现在你需要告诉国王完成编号更新的最低成本是多少，或者说明这是不可能的。

inputFormat:
第一行一个整数 $n$。

接下来 $n$ 行，每行四个整数 $m_i,a_i,b_i,k_i$，代表 $i$ 号学校的旧编号为 $m_i$，新编号的范围为 $[a_i,b_i]$，改变编号的单位成本为 $k_i$。

outputFormat:
如果不存在一种方案，使得任意两个学校的编号不同，输出 `NIE`。

否则输出一个整数，代表最小成本。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le a_i \le m_i \le b_i \le n \le 200$，$1\le k_i \le 1000$。


title: [POI2006] MET-Subway

description:
A certain city has been coping with subway construction for a long time. The finances have been mismanaged and the costs have been underestimated to such extent that no funds were foreseen for the purchase of trains. As a result, too many stations and only some of the planned tunnels have been built - barely enough to allow a connection between any two stations to exist. The number of tunnels (each of them is bidirectional) is one less than the number of stations built. From the remaining funds only a handful of trains have been acquired.

To save their face, the board of directors have asked you to plan subway routes in such a way as to allow maximal number of stations to be connected. Each train travels on a specified route. The routes cannot branch (no three tunnels starting at a single station may belong to the same route). Distinct routes may comprise the same station or tunnel.

TaskWrite a programme which:

reads a description of the tunnel system and the number of subway lines, which are to be planned from the standard input,calculates the maximal number of stations which can be covered by the specified number of subway lines,writes the outcome to the standard output.

给定一棵树，选择l条路径覆盖最多的点的个数是多少。

inputFormat:
The first line of the standard input contains two integers $n$ and $l$ ($2 \le n \le 1\ 000\ 000, 0 \le l \le n$) separated by a single space. $n$ denotes the number of stations and $l$ denotes the number of subway lines, which are to be planned. The stations are numbered from $1$ to $n$.

Each of the following $n-1$ lines contains two distinct integers separated by a single space.

The numbers $1 \le a_i, b_i \le n$ in the $(i+1)$'th line denote the numbers of stations connected by $i$'th tunnel.

outputFormat: The first and only line of the standard output should contain a single integer denoting the maximal number of stations which can be covered by train routes.


title: [POI2006] NAJ-The Invasion

description:
And so it has come - the Triangles have invaded Byteotia!

Byteotia lies on an island, occupying its entire surface.

The shape of the island is a convex polygon(i.e. a polygon whose each inner angle is smaller than $180\degree$).

A certain number of software factories are located in Byteotia, each of which generates constant gains or losses.

The Triangles have decided to occupy such a part of Byteotia which:

is a triangle-shaped area, the vertices of which are three different vertices of the polygon-island,     brings the largest income i.e. the sum of all gains and losses generated by factories within the occupied area is maximal.

We assume that a factory located on the border or in the vertex of occupied area belongs to that area. A territory which contains no factory brings, obviously, a zero income.

Byteasar, the King of Byteotia, is concerned by the amount of losses the Triangles' invasion could generate. Help him by writing a programme which shall calculate the sum of gains and losses generated by factories which the Triangles wish to capture.

TaskWrite a programme which:

reads a decription of Byteotia's shape and the locations of factories from the input file,     determines the maximal value of sum of all gains and losses generated by factories within a triangle, whose vertices are three different vertices of the polygon island,     writes the outcome to the output file.

给定一个凸包， 并给出凸包内部或边上的若干个资源，每个资源都有权值,现在要在凸包上面选择不同的3个点，使得3个点组成的三角形

内部的资源的权值之和最大。

凸包点个数 $n \le 600$

资源个数 $m \le 10000$

inputFormat:
The first line of the input file contains a single integer $n$ ($3 \le n \le 600$), denoting the number of vertices of the polygon-island.

The following $n$ lines of the input contain two integers each $x_j$ and $y_j$ ($-10\ 000 \le x_j, y_j \le 10\ 000$), separated by a single space, denoting the coordinates $x$ and $y$ of consecutive vertices of the island, in a clockwise order.

The $(n+2)$-nd line contains a single integer $m$ ($1 \le m \le 10\ 000$), denoting thetotal number of factories.

In each of the following $m$ lines there are three integers $x_i'$, $y_i'$ and $w_i$ ($-10\ 000 \le x_i', y_i' \le 10\ 000$, $-100\ 000 \le w_i \le 100\ 000$), separated by single spaces, denoting: the coordinates $x$ and $y$ of the $i$-th factory and the gain (for $w_i \ge 0$) or loss (for $w_i < 0$) this factory generates, respectively. Each factory is situated on the polygon-island i.e. within or on the border of it. Distinct factories may be located in the same place i.e. have the same coordinates.

outputFormat: The first and only line of the output file should contain a single integer denoting the maximal value of sum of all gains and losses generated by factories within a triangle whose vertices are three different vertices of the polygon-island. Notice that it may happen that the outcome is a negative integer.

hint:
the correct result is:

![](https://cdn.luogu.com.cn/upload/pic/6970.png)


title: [POI2006] LIS-The Postman

description:
每天早上，忙碌的邮递员需要经过城市的所有街道，完成投递邮件的任务。城市内的所有道路都是单向的，并通过一些路口连接起来。两个路口 $u,v$ 最多只有两条道路直接相连：一条 $u \to v$，一条 $v \to u$（也即不存在两条 $u \to v$ 的街道）。所有路口从 $1$ 到 $n$ 编号。

在路口 $1$，邮递员可以开始他的行程，或是结束他的行程。很长的一段时间里，邮递员可以随意选择他的路线，但最近新出的一条规定打乱了他的计划：每个邮递员得到了若干组路口序列，现在邮递员的路线必须满足如下要求：

- 路线必须从路口 $1$ 开始，在路口 $1$ 结束。
- 路线必须经过每条街道**恰好**一次。
- 规定的每个路口序列都必须在路线中**连续**出现。例如：`1 2 1` 这个序列在 `1 2 1 3` 中出现了，而在 `1 2 3 1` 中没有出现（不是连续的）。

现在邮递员找到了你，希望你能告诉他是否存在满足上述条件的路线，如果有的话，也请告诉他一条满足要求的路线。

inputFormat:
输入第一行两个整数 $n,m$，分别为路口数和街道数。

接下来 $m$ 行，每行两个整数 $a,b$，表示存在一条 $a \to b$ 的街道。保证相同的街道不会重复给出，也不会有自环。

下一行一个整数 $t$，代表规定的路口序列数。

接下来 $t$ 行，每行第一个整数 $k$，接下来 $k$ 个数，代表一个规定的路口序列。

outputFormat:
如果存在一个满足条件的路线，输出 `TAK`，否则输出 `NIE`。

如果答案是 `TAK` 的话，请在接下来每行输出一个整数，代表一个满足条件的路线。

设你输出了 $m+1$ 个数，输出的第 $i$ 个数为 $v_i$，你的输出需要满足如下条件：

- $v_1=v_{m+1}=1$。
- $\forall 1 \leq i \leq m$，都存在 $v_i$ 到 $v_{i+1}$ 的街道。
- 城市中的每条街道**恰好**出现一次。
- 规定的每个路口序列都必须在路线中**连续**出现。

hint: 所有数据均满足：$2 \leq n \leq 5 \times 10^4$，$1 \leq m \leq 2 \times 10^5$，$1 \leq a,b \leq n$，$a \neq b$，$0 \leq t \leq 10^4$，$2 \leq k \leq 10^5$，$\sum k \leq 10^5$。


title: [POI2006] ORK-Ploughing

description:
Byteasar, the farmer, wants to plough his rectangular field. He can begin with ploughing a slice from any of the field's edges, then he can plough a slice from any unploughed field's edges, and so on, until the whole field is ploughed. After the ploughing of every successive slice, the yet-unploughed field has a rectangular shape. Each slice has a span of $1$, and the length and width of the field are the integers $n$ and $m$.

Unfortunately, Byteasar has only one puny and frail nag (horse) at his disposal for the ploughing. Once the nag starts to plough a slice, it won't stop until the slice is completely ploughed. However, if the slice is to much for the nag to bear, it will die of exhaustion, so Byteasar has to be careful. After every ploughed slice, the nag can rest and gather strength. The difficulty of certain parts of the field varies, but Byteasar is a good farmer and knows his field well, hence he knows every part's ploughing-difficulty.

Let us divide the field into $m\times n$ unitary squares - these are called tiles in short.

We identify them by their coordinates $(i,j)$, for $1\le i\le m$ and $1\le j\le n$.

Each tile has its ploughing-difficulty - a non-negative integer.

Let $t_{i,j}$ denote the difficulty of the tile which coordinates are $(i,j)$.

For every slice, the sum of ploughing-difficulties of the tiles forming it up cannot exceed a certain constant $k$ - lest the nag dies.

A difficult task awaits Byteasar: before ploughing each subsequent slice he has to decide which edge of the field he'll plough, so that the nag won't die. On the other hand, he'd like to plough as few slices as possible.

TaskWrite a programme that:

reads the numbers $k$,$m$ and $n$ from the input file, as well as the ploughing-difficulty coefficients,     determines the best way to plough Byteasar's field,     writes the result to the output file.

Byteasar想耕种他那块矩形的田，他每次能耕种矩形的一边（上下左右都行），在他每次耕完后，剩下的田也一定是矩形，每块小区域边长为$1$，耕地的长宽分别为$m$和$n$，不幸的是Byteasar只有一匹老弱的马，从马开始耕地开始，只有当它耕完了一边才会停下休息。但有些地会非常难耕以至于马会非常的累，因此Byteasar需要特别小心。当耕完了一边之后，马可以停下来休息恢复体力。每块地耕种的难度不一，但是Byteasar都非常清楚。我们将地分成$m\times n$块单位矩形——我们用坐标$(i,j)$来定义它们。每块地都有一个整数$t_{i,j}$,来定义$(i,j)$的耕种难度。所以每次马耕一边地时的难度就是所有它耕种的地的难度总和，对于这匹虚弱的马而言，这个值不能超过他的体力值。Byteasar想知道在马不死掉的情况下最少需要耕多少次才能把地耕完。

inputFormat:
There are three positive integers in the first line of the input file: $k$,$m$ and $n$,separated by single spaces, $1\le k\le 200\ 000\ 000$,$1\le m,n\le 2000$.

In the following $n$ lines there are the ploughing-difficulty coefficients.

The line no. $j+1$ contains the coefficients $t_{1,j},t_{2,j}...,t_{n,m}$, separated by single spaces,$0\le t_{i,j}\le 100\ 000$.

outputFormat: Your programme should write one integer to the output file: the minimum number of slices required to plough the field while satisfying the given conditions. Since we care for animals, we guarantee that the field can be ploughed according to the above rules. But remember, saving the nag is up to you!

hint: 感谢@NaVi\_Awson 提供翻译


title: [POI2006] TAN-Dancing in Circles

description:
$n$ kids attend a certain kindergarten. Everyday the kids arrange themselves in $k$ circles and dance.

At least $l$ kids dance in each circle. Two arrangements of children are considered distinct if there isa child who has a different right neighbour in one of the arrangements than in the other.

Your task is to calculate the number of all distinct arrangements modulo $2005$. Should there beno arrangements satisfying the aforementioned conditions, the correct outcome is $0$.

TaskWrite a programme which:

reads the numbers $n$, $k$ and $l$ from the standard input,        calculates the number $d'=d\ mod\ 2005$, where $d$ denotes the number of distinct arrangements    of the children ($d\ mod\ 2005$ denotes the remainder of the division of $d$ by $2005$),        writes $d'$ to the standard output.

幼儿园中有N个小朋友在做游戏，每天小朋友们都会有一个尬舞方案（围成K个圈尬舞）。

每个圈子里至少有L个小朋友，如果在一个方案里有一个小朋友他右面的小朋友和另一个方案里他右面的小朋友不同，那么两个尬舞方案就会被认为是不同的。

你的任务是计算所有不同的尬舞方案的数量，因为结果可能比较大，所以最后输出答案mod2005的结果。

如果没有符合要求的尬舞方案，输出0。

inputFormat:
The first and only line of the standard input contains three integers separated by single spaces: $n$- the number of children ($3\le n\le 1\ 000\ 000\ 000$), $k$ - the number of circles($1\le k\le n$) and $l$ - the minimal number of kids in a circle ($2\le l\le n$).

只有一行输入，三个整数N,K,L(3≤N≤1,000,000,000 ; 1≤K≤n ; 2≤L≤n)分别代表小朋友数量，圈子数量，每个圈子里最少的小朋友数。

outputFormat:
The first and only line of the standard output should contain a single integer: $d\ mod\ 2005$.

只有一行输出，即合理的尬舞方案数d(mod2005)

hint: 感谢@Paperback\_Writer 提供翻译


title: [POI2006] EST-Aesthetic Text

description:
Let us consider a text consisting of n words numbered from 1 to n. We represent any of its decompositions into k lines by a sequence of numbers (a\_1,a\_2...a\_{k-1}), such that the words with numbers from 1 to a\_1 are in the first line, the words with umbers from a\_1 + 1 to a\_2 are in the second line, and so on, and finally, the words with numbers from a\_{k-1} + 1 to n are in the last, k-th line.

Each word has a certain length (measured in the number of characters). Let length(x) denote the length of the word no. . Furthermore, every two subsequent words in a line are separated by a space of width of a single character. By length of the line we denote the sum of lengths of the words in this line, increased by the number of spaces between them. Let line(w) denote the length of the line no.w . I.e., if the line no.w contains the words with numbers from i to j inclusive, its length is:

```cpp
XXXX (1st line)
XXX XX (2nd line)
XXXXX (3rd line)
```

line(w)=length(i)+..length(j)+(j-i)

As an example, let us consider a text consisting of 4 words of lengths 4, 3, 2 and 5, respectively, and its decomposition (1,3) into 3 lines. Then the length of the first line is 4, second -6 , and third -5 :

We shall refer to the number

|line(1)-line(2)|+...+|line(k-1)-line(k)|

as the coefficient of aestheticism of a decomposition of the given text into k lines. Particularly, if the decomposition has only one line, its coefficient of aestheticism is 0.

Needles to say, the smaller the coefficient, the more aesthetical the decomposition. We shall consider only these decompositions that have no line whose length exceeds some constant m. Of all such decompositions of a given text into any number of lines we seek the one most aesthetical, i.e. the one with the smallest coefficient of aestheticism. The aforementioned examplary decomposition's coefficient is 3, and that is exactly the minimum coefficient of aestheticism for m=6 and m=7.

inputFormat: The first line of the standard input contains the numbers $m$ and $n$, $1\le m\le 1\ 000\ 000$,$1\le n\le 2\ 000$, separated by a single space. The second, last line of the standard input contains $n$ integers, denotingthe lengths of subsequent words, $1\le length(i)\le m$ for $i=1,2,\cdots,n$, separated by single spaces.

outputFormat: The first and only line of the standard output should contain exactly one integer: the minimumcoefficient of aestheticism for those decompositions, whose every line's length does not exceed $m$.

translation:
       现在, 我们有一个由$n$个单词组成的英文文本. 但是它们都挤在一行里, 单词间以一个半角空格分隔, 就像丑陋的压行代码. 你可以把他们通过$k-1$次换行分割成$k$行的文本并去除行首行末空格. 为方便题意表述, 我们以一个长度为$k-1$的数列$\{a_1,a_2,...,a_{k-1}\}$, 表示第$1$到第$a_1$个单词放在第$1$行, 第$a_1+1$到第$a_2$个单词放在第$2$行, 以此类推.
       不过, 为了让新的文本更加美妙, 你希望**在满足每一行的长度不大于$m$的情况下相邻行长度之差的和最小**. 具体地, 令$length(i)$表示第$i$个单词的长度, $line(i)$表示第$i$行的长度, 则:
$$
line(i)=(a_i-a_{i-1}-1)+\sum_{j=a_{i-1}+1}^{a_i}length(j)
$$
你需要求得的答案$Ans$为:
$$
Ans=\min_{k,line(i)\le m}\{\sum_{i=1}^{k-1}|line(i)-line(i+1)|\}
$$
现在输入单词数$n$, 行长度限制$m$, 每个单词的长度$length(i)$, 请输出答案.


title: [POI2006] KRY-Crystals

description:
Byteman is a scientist who investigates creation of crystals consisting of atoms of different elements.

He has designed a special process for creating crystals and has discovered a formula specifying theamount of elements that can be used to create a crystal. Now, he wonders how many differentcrystals can be created in such process.

For non-negative integers $x$ and $y$, by $x\bigoplus y$ we shall denote their bit-wise xor. The basic xor forsingle bits is defined by:

$1\bigoplus 1=0\bigoplus 0=0$,$0\bigoplus 1=1\bigoplus 0=1$.

Byteman knows $n$ different elements that can be used to create crystals -these are numbered from $1$ to $n$. For each element $i$ there is an upper bound $m_i$ on number of atoms of this elementthat can be used to create a crystal. Byteman can create one unique crystal composed of $a_i$ atomsof the element $i$ (for $i=1,\cdots,n$), if and only if:

- $0\le a_i\le m_i$ for $i=1,\cdots,n$

- $a_1\bigoplus\cdots\bigoplus a_n=0$, and

- $a_1+a_2+\cdots+a_n\ge 1$.

Note that the last condition is quite obvious and essentially states that every crystal is composed ofat least one atom.

TaskWrite a programme which:

reads form the standard input: the number of elements and the bounds on numbers of atoms    of particular elements,        computes the number of different crystals that can be created,        writes the result to the standard output.

inputFormat:
The first line of the standard input contains the number of elements $n$, $1\le n\le 50$.

The second, last line of the standard input contains $n$ positive integers $m_1,\cdots,m_n$, separated by single spaces,$1\le m_i<2^{32}-1$.

outputFormat: Your programme should write one integer to the standard output - total number of different crystals  that can be created. You can assume that this number is less than $2^{64}$.

translation:
### 题目描述

给定 $n$ 个正整数 $m_1$ 到 $m_n$，对长度为 $n$ 且满足以下条件的整数序列 $a$ 计数：
- 对于任意 $1\le i\le n$，$0\le a_i\le m_i$；
- $a_1\oplus a_2\oplus\cdots\oplus a_n=0$，其中 $\oplus$ 为按位异或运算；
- $a_1+a_2+\cdots+a_n\ge1$。

### 输入格式
第一行有一个正整数 $n$。

第二行有 $n$ 个正整数，表示 $m_1,m_2,\ldots,m_n$。
### 输出格式
输出一行一个正整数表示序列的个数。
### 说明/提示
$1\le n\le50$。

$1\le m_i\le2^{32}-1$。

数据保证答案小于 $2^{64}$。

感谢 @FZzzz @UnyieldingTrilobite 提供翻译。


title: [POI2006] MIS-Teddies

description:
Byteoian 是一家专业生产儿童玩具的公司。他们生产的玩具质量上乘，广受好评。

但最近，有人发现他们生产的泰迪熊存在致命缺陷。总共有四种泰迪熊型号：$A1$，$A2$，$B1$，$B2$，一旦将三个字母相同或数字相同的泰迪熊放在一块，就会对泰迪熊造成致命损坏。

如果一种摆放泰迪熊的方案中不存在连续三个字母相同或数字相同的泰迪熊，则称这种摆放方案是**安全的**。

现在你收集了一些泰迪熊，你想要知道有多少种安全的摆放泰迪熊的方案。由于安全的方案可能较多，请输出方案数对 $1\,000\,000$ 取模的结果。

inputFormat: 输入包含四个整数：$n_{A1},n_{A2},n_{B1},n_{B2}$，分别代表 $A1$ 型，$A2$ 型，$B1$ 型，$B2$ 型泰迪熊的数量。

outputFormat: 输出一个整数，即安全摆放泰迪熊的方案数对 $1\,000\,000$ 取模的结果。


title: [POI2006] PAL-Palindromes

description:
Little Johnny enjoys playing with words. He has chosen $n$ palindromes (a palindrome is a wordthat reads the same when the letters composing it are taken in the reverse order, such as dad, eye orracecar for instance) then generated all $n^2$ possible pairs of them and concatenated the pairs intosingle words. Lastly, he counted how many of the so generated words are palindromes themselves.

However, Johnny cannot be certain of not having comitted a mistake, so he has asked you to repeatthe very same actions and to give him the outcome. Write a programme which shall perform thistask for you.

TaskWrite a programme which:

reads the palindromes given by Johnny from the standard input,        determines the number of words formed out of pairs of palindromes from the input, which are palindromes    themselves,        writes the outcome to the standard output.

inputFormat: The first line of the standard input contains a single integer $n$, $n\ge 2$, denoting the number ofpalindromes given by Johnny. The following $n$ lines contain a description of the palindromes. The $(i+1)$'st line contains a single positive integer $a_i$ denoting the length of $i$'th palindrome and apalindrome of $a_i$ small letters of English alphabet. The number $a_i$ is separated from the palindromeby a single space. The palindromes in distinct lines are distinct. The total length of all palindromesdoes not exceed $2\ 000\ 000$.

outputFormat: The first and only line of the standard output should contain a single integer: the number of distinctordered pairs of palindromes which form a palindrome upon being concatenated.

translation:
### 题目描述

Johnny 喜欢玩文字游戏。

他写下了 $n$ 个回文串，随后将这些串两两组合，合并成一个新串。容易看出，一共会有 $n^2$ 个新串。

两个串组合时顺序是任意的，即 `a` 和 `b` 可以组合成 `ab` 和 `ba`，另外自己和自己组合也是允许的。

现在他想知道这些新串中有多少个回文串，你能帮帮他吗？

### 输入格式

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行包含一个数 $a_i$ 和一个长度为 $a_i$ 的回文串。

保证所有串只包含小写字母，且所有串两两不同，所有回文串的长度和不超过 $2 \times 10^6$。

### 输出格式

输出一个整数，代表满足条件的新串的数量。

samples:
6
2 aa
3 aba
3 aaa
6 abaaba
5 aaaaa
4 abba


title: [POI2006] ZOS-Sophie

background:
感谢uid=45443提供的翻译

此题需要spj，征求spj ing

description:
Little Sophie gives a birthday party. She has written a tentative list of her kindergarten friendsshe would like to invite. However, kids are very demanding guests. Mary said she should come, butonly provided Camille and Emily are not present, for they took her doll last week. Little Christopheronly plays with Sophie and Camille and he does not wish to see any other kids at the party. And soon...

Sophie considers a party a success if none of the guests invited has objection against any other'spresence. She has decided not to invite certain kids to assure that the party is a success. On theother hand she would like to invite as many kids as possible. Should Sophie not be able to invite atleast $k$ kids she won't give any party at all.

## Task

Help little Sophie! Write a programme which:

- reads the number of all Sophie's acquaintances $n$, the number $k$ and a description of kids' demands from the standard input,

- verifies if it is possible to invite at least $k$ kids so that the party could be a success,

- if it is not possible, writes the word NIE (i.e. no in Polish)  to the standard output; if it is possible, finds the largest group of kids who could be invited to the party so that it is a success and  writes it to the standard output.

Sophie举办了一个生日派对，她为此写了一个不确定的表，表上是她邀请的幼儿园朋友。然而孩子们都是苛刻的客人。Mary说她要来，但是因此Camille和Emily就不来了，因为他们上周拿走了Mary的娃娃。Christopher只和Sophie和Camille一起玩，他不想在聚会上看到别的孩子。很快…

Sophie认为如果没有反对任何人出席的客人，那这个派对就是成功的。因此她决定不邀请某些孩子来保证晚会是成功的。另一方面，她想邀请尽可能多的孩子。如果Sophie不能邀请至少k的孩子，她根本就无法举办任何派对。

帮一下Sophie吧。写一个能够实现以下目标的程序：

在标准输入流中读入n和k，分别表示孩子的总数和派对的最少人数。

确定能否举办派对。如果不能，输出"NIE“（即波兰语中的“否”）

如果可能的话，找一组尽可能多被邀请参加聚会的孩子，这样就成功了，并把它写在标准输出流上。

inputFormat:
The first line of the standard input contains two positive integers separated by a single space:

$n$ - the number of all Sophie's acquaintances ($2 \le n \le 100\ 000$) and $k$ -the minimal number of kids Sophie wishes to invite to the party($n-10 \le k < n$). The kids are assigned numbers from therange $1$ to $n$.

The following lines contain a description of kids' demands. In the second line there is a singleinteger $m$, $1 \le m \le 3\ 000\ 000$

Each of the following $m$ lines contains a pair of integers $a$, $b$, separated by a single space ($1 \le a,b, \le n, a \neq b$). You can assume that each (ordered) pair appears in the standard input once at the most. The pair $a$, $b$ denotes that the child $a$ does not wish to meet child $b$ at the party.

标准输入流的第一行是两个整数 $n$ 和 $k$（$2\le n\le10$，$n-10\le k<n$）。表示孩子的总数和派对的最少人数。接下来一行是一个整数 $m$ 表示孩子们的要求（$1<=m<=3000000$）。

接下来m行每行有一堆整数a和b，用空格隔开（1<=a,b<=n,a!=b）。表示第a个孩子不能和第b个孩子同时参加派对。保证有序对a，b不重复。

outputFormat:
If it is not possible to invite $k$ kids to the party so that it is a success then the first and only line ofthe standard output should contain a single word: NIE.

If it is possible, then the first line of the standard input should contain a single integer - themaximal number of kids that can be invited to the party so that it is a success.

The second line of the standard output should contain the numbers of kids to be invited, separated by single spaces, inincreasing order. Should there be more correct answers your programme should write out any oneof them.

如果不可能有k个孩子参加派对，输出"NIE"。

如果可以，在第一行是一个整数，表示可以参加派对的孩子数量。

第二行是可以参加派对的孩子编号，用空格隔开，以递增的方式输出，如果有多个答案，输出其中任意一个


title: [POI2007] ATR-Tourist Attractions

background: [English Edition](/paste/gu4ksinh)

description:
给出一张有 $n$ 个点 $m$ 条边的无向图，每条边有边权。

你需要找一条从 $1$ 到 $n$ 的最短路径，并且这条路径在满足给出的 $g$ 个限制的情况下可以在所有编号从 $2$ 到 $k+1$ 的点上停留过。

每个限制条件形如 $r_i, s_i$，表示停留在 $s_i$ 之前必须先在 $r_i$ 停留过。

**注意，这里的停留不是指经过**。

inputFormat:
第一行三个整数 $n,m,k$。

之后 $m$ 行，每行三个整数 $p_i, q_i, l_i$，表示在 $p_i$ 和 $q_i$ 之间有一条权为 $l_i$ 的边。

之后一行一个整数 $g$。

之后 $g$ 行，每行两个整数 $r_i, s_i$，表示一个限制条件。

outputFormat: 输出一行一个整数，表示最短路径的长度。


title: [POI2007] BIU-Offices

description:
Bytel is a mobile telephony potentate. Each employee has been issued a company phone, the memory ofwhich holds the numbers of some of his co-workers (all of them have his number in their phones as well).

Due to dynamic growth of their operations the board of directors intends to move company headquaters tonew office buildings. It has been decided - in order to boost work efficiency - that every pair of employeesworking in different buildings should know (reciprocally) each others phone number i.e. the memory of theircompany phone ought to hold necessary phone numbers.

Simultaneously, the board have decided to rent as many office buildings as possible to ensure good workingconditions. Help the board of Bytel to plan the number of office buildings and their size in accordancewith the aforementioned requirements.

## Task

Write a programme which:

reads the description of employees' phone number lists from the standard input        calculates the maximal number of office buildings and their sizes, satisfying board's conditions        writes the outcome to the standard output.

inputFormat:
The first line of the standard input consists of two integers: $n$ and $m$ ($2 \le n \le 100\ 000$, $1 \le m \le 2\ 000\ 000$),separated by single spaces, denoting the number of Bytel employees and the number of pairs of employeeswho have their numbers in company phones, respectively. The employees are numbered from $1$ to $n$.

Each of the following $m$ lines contains a single pair of integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le n$ for $1 \le i \le m$), separated by a single space, denoting that employees $a_i$ and $b_i$ have their numbers (reciprocally) in company phones' memory. Each pair of integers denoting a pair of employees shall occur once at the most in the standard input.

outputFormat:
The first line of the standard output should contain a single integer: the maximal number of office buildingsthat Bytel should rent. The second should contain a non-decreasing sequence of positive integers, separatedby singe spaces, denoting the sizes of the office buildings (i.e. the numbers of employees working there).

Should there exist more than one correct answer - write out any one of them.

translation:
## 题目描述

Bytel 是一家移动通信公司。该公司的每位员工都收到了一部公司生产的电话，电话的通讯录中存储着一些同事的电话号码（每部手机中也都有该手机本身的电话号码）。

由于业务扩张，公司总部需要迁移至新的办公区。为了提高工作效率，董事会决定在不同栋楼工作的每一对员工需要**相互**知道对方的电话号码。即如果 $u$ 和 $v$ 在不同的楼工作，则 $u$ 的通讯录里需要存储 $v$ 的电话号，$v$ 的通讯录里也要存储 $u$ 的电话号码。

同时，董事会决定租用尽可能多的楼，以确保良好的工作条件。现在你需要帮助 Bytel 公司计算出他们需要租用多少栋楼。

## 输入格式

输入第一行包含两个整数 $n,m$，分别代表公司的员工数和通讯录的信息数，员工从 $1$ 到 $n$ 编号。

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示 $a_i$ 和 $b_i$ **相互**知道对方的电话号码，保证任意两条信息不重复。

## 输出格式

输出第一行包含一个整数 $t$：董事会需要租用多少栋办公楼。

第二行包含 $t$ 个整数，第 $i$ 个整数 $c_i$ 表示在第 $i$ 栋建筑工作的员工数量。你的输出需要保证 $c_i$ 是单调不下降的。

如果有多种合法方案，你可以输出任意一种。

## 数据范围

$2 \leq n \leq 10^5$，$1 \leq m \leq 2 \times 10^6$，$1 \leq a_i \lt b_i \leq n$。


title: [POI2007] DRZ-Trees

description:
Byteasar has a cottage. Lately, he has bought $n$ trees and had them planted all in one row. Byteasar does not,  however, like the order which the trees have been planted in. It particularly annoys him that tall and short  ones have been mixed up, and the composition does not meet his aesthetic criteria.

Byteasar has invented a disorder coefficient so as to allow the gardener to comprehend his intentions: thelower the value of the coefficient the prettier the row of trees. It is defined in the following way:

$|h_1-h_2|+|h_2-h_3|+\cdots+|h_{n-1}-h_n|$, where $h_1,h_2,\cdots,h_n$ are the heights of consecutive trees in a row.
Replanting is a very toilsome and cumbersome task, therefore Byteasar has ordered the gardener to replanttwo trees at the most (i.e. interchange their positions). The task of the gardener is to choose the pair to replantin a way that makes the disorder coefficient the smallest.

The gardener is not sure if he has chosen the correct pair of trees and he fears he may lose his job ifhe is mistaken. Help him: for each tree calculate the minimal disorder coefficient that may be attained byswitching places with any other tree.

TaskWrite a programme which:

reads the height of the consecutive trees in a row from the standard input,        for each tree calculates the minimal disorder coefficient that may be attained should it switch places    with some other tree (or should there be no change at all),        writes the outcome to the standard output.

定义一排树的不整齐程度为相邻两树的高度差的和。设树高分别为 $h _ 1, h _ 2, \cdots, h _ n$，那么不整齐程度定义为：$|h_1-h_2|+|h_2-h_3|+\cdots+|h_{n-1}-h_n|$。

请对于每个 $i$ 求出，如果只把 $i$ 和另一棵树交换高度（可以不交换），那么不整齐度最小是多少。

inputFormat:
The first line of the standard input contains one integer $n$ ($2\le n\le 50\ 000$).

The other contains $n$ integers $h_i$ ($1\le h_i\le 100\ 000\ 000$)separated by single spaces, denoting the height of the consecutive trees in the row.

outputFormat: The output should consist of precisely $n$ lines. The $i$'th line should contain a single integer - the smallestdisorder coefficient attainable when considering replanting of the $i$'th tree.


title: [POI2007] OSI-Axes of Symmetry

description:
Little Johnny - a well-respected young mathematician - has a younger sister, Justina. Johnny likes hissister very much and he gladly helps her with her homework, but, like most scientific minds, he does mindsolving the same problems again. Unfortunately, Justina is a very diligent pupil, and so she asks Johnny toreview her assignments many times, for sake of certainty. One sunny Friday, just before the famous LongMay Weekend1 the math teacher gave many exercises consisting in finding the axes of symmetry of variousgeometric figures. Justina is most likely to spend considerable amount of time solving these tasks. LittleJohnny had arranged himself a trip to the seaside long time before, nevertheless he feels obliged to help hislittle sister. Soon, he has found a solution - it would be best to write a programme that wouldease checking Justina's solutions. Since Johnny is a mathematician, not a computer scientist, and you are hisbest friend, it falls to you to write it.

## Task

Write a programme that:

- reads the descriptions of the polygons from the standard input,

- determines the number of axes of symmetry for each one of them,

- writes the result to the standard output.

给定一个多边形，求对称轴数量。

inputFormat: In the first line of the input there is one integer $t$ ($1 \le t \le 10$) - it is the number of polygons, for which the number of axes of symmetry is to be determined. Next, $t$ descriptions of the polygons follow. The first line of each description contains one integer $n$ ($3 \le n \le 100\ 000$) denoting the number of vertices of the polygon. In each of the following $n$ lines there are two integers $x$ and $y$ ($-100\ 000\ 000 \le x, y \le 100\ 000\ 000$) representing the coordinates of subsequent vertices of the polygon. The polygons need not be convex, but they have no self-intersections - any two sides have at most one common point - their common endpoint, if they actually share it. Furthermore, no pair of consecutive sides is parallel.

outputFormat: Your programme should output exactly $t$ lines, with the $k$'th line containing a sole integer $n_k$ - the number of axes of symmetry of the $k$'th polygon.

translation:
### 题目描述

Johnny 是一位非常年轻的数学家，但他此刻正在为他妹妹的数学作业烦恼。

这个周末，他的妹妹需要完成一项作业，计算各种几何图形的对称轴数量。因为 Johnny 这个周末想要去海边旅行，所以他希望他的妹妹能尽快完成这项作业。

于是他找到了擅长编程的你，你一定能帮助他完成这项任务的！

### 输入格式

输入包含多组数据。

第一行包含一个整数 $t$，代表数据的组数。

对于每组数据，第一行一个整数 $n$，代表多边形的顶点数。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，代表每个顶点的坐标。

输入中的第 $i$ 个顶点会与第 $i+1$ 个顶点连一条边。特别地，输入中的第 $n$ 个顶点会与第一个顶点连一条边。

输入给出的多边形**不保证**是凸多边形，但是保证任意两条边只会在端点处相交，且任意两条相邻的边不共线。

### 输出格式

对于每组数据，输出一行一个整数，即多边形对称轴的数量。

### 数据范围

$1 \leq t \leq 10$，$3 \leq n \leq 10^5$，$-10^8 \leq x_i,y_i \leq 10^8$。


title: [POI2007] ZAP-Queries

description:
密码学家正在尝试破解一种叫 BSA 的密码。

他发现，在破解一条消息的同时，他还需要回答这样一种问题：

给出 $a,b,d$，求满足 $1 \leq x \leq a$，$1 \leq y \leq b$，且 $\gcd(x,y)=d$ 的二元组 $(x,y)$ 的数量。

因为要解决的问题实在太多了，他便过来寻求你的帮助。

inputFormat:
输入第一行一个整数 $n$，代表要回答的问题个数。

接下来 $n$ 行，每行三个整数 $a,b,d$。

outputFormat: 对于每组询问，输出一个整数代表答案。

hint:
#### 数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 5 \times 10^4$，$1 \leq d \leq a,b \leq 5 \times 10^4$。


title: [POI2007] GRZ-Ridges and Valleys

description:
Byteasar loves trekking in the hills. During the hikes he explores all the ridges and valleys in vicinity.

Therefore, in order to plan the journey and know how long it will last, he must know the number of ridgesand valleys in the area he is going to visit. And you are to help Byteasar.

Byteasar has provided you with a map of the area of his very next expedition. The map is in the shape ofa $n\times n$ square. For each field $(i,j)$ belonging to the square(for $i,j\in \{1,\cdots,n\}$), its height $w_{(i,j)}$ is given.

We say two fields are adjacent if they have a common side or a common vertex (i.e. the field $(i,j)$ is adjacent to the fields $(i-1,j-1)$,$(i-1,j)$,$(i-1,j+1)$,$(i,j-1)$,$(i,j+1)$,$(i+1,j-1)$,$(i+1,j)$,$(i+1,j+1)$, provided that these fields are on the map).

We say a set of fields $S$ forms a ridge (valley) if:

all the fields in $S$ have the same height,the set $S$ forms a connected part of the map (i.e. from any field in $S$ it is possible to reach any other    field in $S$ while moving only between adjacent fields and without leaving the set $S$),if $s\in S$ and the field $s'\notin S$ is adjacent to $s$, then $w_s>w_{s'}$(for a ridge) or $w_s<w_{s'}$ (for a valley).

In particular, if all the fields on the map have the same height, they form both a ridge and a valley.

Your task is to determine the number of ridges and valleys for the landscape described by the map.

TaskWrite a programme that:

reads from the standard input the description of the map,        determines the number of ridges and valleys for the landscape described by this map,        writes out the outcome to the standard output.

给定一张地势图，求山峰和山谷的数量

inputFormat: In the first line of the standard input there is one integer $n$ ($2\le n\le 1\ 000$)denoting the size of the map. Ineach of the following $n$ lines there is the description of the successive row of the map. In $(i+1)$'th line(for $i\in \{1,\cdots,n\}$) there are $n$ integers $w_{(i,1)},\cdots,w_{(i,n)}$($0\le w_i\le 1\ 000\ 000\ 000$), separated by single spaces. Thesedenote the heights of the successive fields of the $i$'th row of the map.

outputFormat: The first and only line of the standard output should contain two integers separated by a single space -thenumber of ridges followed by the number of valleys for the landscape described by the map.

translation:
给定一个地图，为小朋友想要旅行的区域，地图被分为n*n的网格，每个格子(i,j) 的高度w(i,j)是给定的。若两个格子有公共顶点，那么他们就是相邻的格子。（所以与(i,j)相邻的格子有(i-1, j-1),(i-1,j),(i-1,j+1),(i,j-1),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1)）。我们定义一个格子的集合S为山峰（山谷）当且仅当：

1.S的所有格子都有相同的高度。

2.S的所有格子都联通3.对于s属于S，与s相邻的s’不属于S。都有ws > ws’（山峰），或者ws < ws’（山谷）。

你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

输入 第一行包含一个正整数n，表示地图的大小（1<=n<=1000）。接下来一个n*n的矩阵，表示地图上每个格子的高度。(0<=w<=1000000000)

输出 应包含两个数，分别表示山峰和山谷的数量。

感谢@Blizzard 提供的翻译


title: [POI2007] POW-The Flood

description:
Byteburg, the capital of Byteotia, is a picturesque city situated in a valley in the midst of mountains. Unfortunately,  recent heavy rainfall has caused a flood - all the Byteburg is now completely under water. Byteasar,  the king of Byteotia, has summoned his most enlightened advisors, including you, to a council. After long  deliberations the council agreed to bring a few pumps, set them up in the flooded area and drain Byteburg.

The king has asked you to determine the minimum number of pumps sufficing to drain the city.

You are provided with a map of the city and the valley it is situated in. The map is in the shape of a $m\times n$ rectangle, divided into unitary squares. For each such square the map tells its height above sea level and alsowhether it is a part of Byteburg or not. The whole area depicted in the map is under water. Furthermore, it issurrounded by much higher mountains, making the outflow of water impossible. Obviously, there is no needto drain the area that does not belong to Byteburg.

Each pump can be placed in any unitary square depicted in the map. The pump will be drawing thewater until its square is completely drained. Of course, the communicating tubes principle makes its work,      so draining one square results in lowering the water level or complete draining of those squares from which      the water can flow down to the one with the pump. Water can flow only between squares with a common side      (or, more exact, squares whose projections onto horizontal plane have a common side, since the squares may       be at different level). Apart from that, the water obviously only flows down.

## Task

Write a programme that:

- reads description of the map from the standard input,

- determines the minimum number of pumps needed to drain whole Byteburg,

- writes out the outcome to the standard output.

给定一张地势图，所有的点都被水淹没，现在有一些关键点，要求放最少的水泵使所有关键点的水都被抽干

inputFormat: In the first line of the standard input there are two integers $m$ and $n$, separated by a single space, $1 \le n, m \le 1\ 000$. The following $m$ lines contain the description of the map. The $(i+1)$'th line describes the $i$'th row of unitary squares in the map. It contains $n$ integers $x_{i,1}, x_{i,2}, ..., x_{i_n}$, separated by single spaces,$-1\ 000 \le x_{i,j} \le 1\ 000$ ,$x_{i,j} \ne 1000$ . The number $x_{i,j}$ describes the $j$'th square of the $i$'th line. The ground level in this square is $|x_{i,j}|$ above sea level. If $x_{i,j} > 0$, then the square is part of Byteburg, otherwise it is outside the city. Notice, that the area of Byteburg need not be connected. In fact the city may have several separate parts.

outputFormat: Your programme should write out one integer to the standard output - the minimum number of pumpsneeded to drain Byteburg.

translation:
Description 你手头有一张该市的地图。这张地图是边长为 m∗n 的矩形,被划分为m∗n个1∗1的小正方形。对于每个小正方形,地图上已经标注了它的海拔高度以及它是否是该市的一个组成部分。地图上的所有部分都被水淹没了。并且,由于这张地图描绘的地面周围都被高山所环绕,洪水不可能自动向外排出。显然,我们没有必要抽干那些非该市的区域。

每个巨型抽水机可以被放在任何一个1∗1正方形上。这些巨型抽水机将持续地抽水直到这个正方形区域里的水被彻底抽干为止。当然,由连通器原理,所有能向这个格子溢水的格子要么被抽干,要么水位被降低。每个格子能够向相邻的格子溢水,“相邻的”是指(在同一高度水平面上的射影)有公共边。

Input

第一行是两个数m,n(1<=m,n<=1000).

以下 m 行,每行 n 个数,其绝对值表示相应格子的海拔高度;若该数为正,表示它是该市的一个区域;否则就不是。

请大家注意:所有格子的海拔高度其绝对值不超过 1000 ,且可以为零.

Output

只有一行,包含一个整数,表示至少需要放置的巨型抽水机数目。

感谢@FlashHu 提供的翻译


title: [POI2007] SKA-Rock Garden

description:
Vicomte de Bajteaux is the owner of a renowned collection of boulders. Up to now, he has kept it in thecellars of his palace, but recently, he has decided to display the collection in his vast gardens.

The gardens have a shape of rectangle, whose sides are $1\ 000\ 000\ 000$ units long and are parallel to east-westand north-south geographical directions. For each boulder, vicomte has determined coordinates ofthe point, which he would like it to be placed in (the coordinates are simply distances to the southern and    western side of the garden), and gave them to his servants. Unfortunately he has forgot to tell them the orderof the coordinates (i.e. for some of the boulders the first coordinate of a point is the so called "$y$ coordinate",i.e. the ordinate, while for others the so called "$x$ coordinate", i.e. the abscissa).

The servants, unaware of thisfact, have placed the boulders assuming customary coordinate ordering (as in standard Cartesian coordinates:

the abscissa, commonly known as "$x$ coordinate", first).

To protect his collection, vicomte has decided to surround it with a fence. For aesthetic reasons thefence has to be a rectangle, with sides parallel to the sides of the garden. The garden layout has been planned,      so that the total length of the fence be minimal (i.e. in the space of all coordinate orderings, the original          ordering of vicomte requires the minimal length of the fence - we assume that the rectangle may have sides of zero length).

The servants have to move the boulders so that the length of the fence required is minimal lest their mistake become obvious. Each boulder may only be moved in a way that preserves the coordinate set: by      interchanging its coordinates. As the boulders are heavy, the servants would like to minimize their effort, by      minimizing the weight of the boulders to be moved.

## Task

Write a programme which:

reads the present positions of the boulders in the gardens and their respective weights, determines a sequence of moves, which minimizes the length of the fence required to protect the    boulders and also minimizes the weight of the boulders to be moved, writes the outcome to the standard output.

Blue Mary是一个有名的石头收藏家。迄今为止，他把他的藏品全部放在他的宫殿的地窖中。现在，他想将他的藏品陈列在他的花园中。皇家花园是一个边长为1000000000单位的平行于坐标轴的正方形。对于每个石头，Blue Mary都有一个他想放置的坐标，然后将他告诉他的属下。不幸的是，他忘了告诉他们坐标的顺序（比如无法分辨(x,y)和(y,x)）。属下们，就自己决定了每个石头的具体位置。为了保护他的藏品，Blue Mary决定建造一个篱笆来保护他们。为了美学的需要，篱笆也被设计为平行于坐标轴的矩形。如果花园的布局知道了，那么就可以知道最短长度的篱笆的布局。他的属下们需要变换石头的坐标使得篱笆的长度最少。每个石头只能从(x,y)变换为(y,x)，由于每个石头的重量不一样。属下们希望他们移动的石头的重量和最少。

inputFormat: The first line of the standard input contains a single integer $n$ ($2 \le n \le 1\ 000\ 000$), denoting the number of boulders in the collection. The following $n$  lines contain three integers $x_i$, $y_i$ and $m_i$ each ($0 \le x_i, y_i \le 1\ 000\ 000\ 000$, $1 \le m \le 2000$), separated by single spaces, denoting the present coordinates and the weight of $i$'th boulder. No unordered pair of coordinates will appear in the input more than once.

outputFormat:
The first line of the standard output should contain two integers, separated by a single space - the minimal length of fence possible and the minimal weight of the boulders to be moved in order to obtain such a length.

The second line should contain a sequence of $n$ zeros and/or ones - $i$'th element of the sequence should be a one if in the optimal solution the $i$'th boulder is to be moved and zero otherwise. Should more than one correct solutions exist, your programme is to write out any one of them.


title: [POI2007] MEG-Megalopolis

description:
Byteotia has been eventually touched by globalisation, and so has Byteasar the Postman, who once roamedthe country lanes amidst sleepy hamlets and who now dashes down the motorways. But it is those strolls inthe days of yore that he reminisces about with a touch of tenderness.

In the olden days $n$ Byteotian villages (numbered from $1$ to $n$) were connected by bidirectional dirt roadsin such a way, that one could reach the village number $1$ (called Bitburg) from any other village in exactlyone way. This unique route passed only through villages with number less or equal to that of the startingvillage. Furthermore, each road connected exactly two distinct villages without passing through any othervillage. The roads did not intersect outside the villages, but tunnels and viaducts were not unheard of.

Time passing by, successive roads were being transformed into motorways. Byteasar remembers distinctly,  when each of the country roads so disappeared. Nowadays, there is not a single country lane left  in Byteotia - all of them have been replaced with motorways, which connect the villages into Byteotian  Megalopolis.

Byteasar recalls his trips with post to those villages. Each time he was beginning his journey with letters  to some distinct village in Bitburg. He asks you to calculate, for each such journey (which took place in a      specific moment of time and led from Bitburg to a specified village), how many country roads it led through.

TaskWrite a programme which:

reads from the standard input:

descriptions of roads that once connected Byteotian villages,    sequence of events: Byteasar's trips and the moments when respective roads were transformed    into motorways,            for each trip, calculates how many country roads Byteasar has had to walk,        writes the outcome to the standard output.

有一棵节点数为 $n$ 的树，给定 $m + n - 1$ 组询问，每组询问有两种操作。

1. `A x y`，将 $x$ 节点和 $y$ 节点间的边权改为 $0$，每条边会被修改恰好一次。

2. `W x`，求 $1$ 号点到 $x$ 号点路径上的边权和。

初始所有边权值都为 $1$。

inputFormat:
In the first line of the standard input there is a single integer $n$ ($1\le n\le 250\ 000$),denoting the number of villages in Byteotia. The following $n-1$ lines contain descriptions of the roads, in the form of two integers $a$,$b$ ($1\le a<b\le n$)separated by a single space, denoting the numbers of villages connected with a road. Inthe next line there is a single integer $m$($1\le m\le 250\ 000$),denoting the number of trips Byteasar has made.

The following $n+m-1$ lines contain descriptions of the events, in chronological order:

A description of the form "A $a$ $b$"(for $a<b$) denotes a country road between villages $a$ and $b$ beingtransformed into a motorway in that particular moment.

A description of the from "W $a$" denotes Byteasar's trip from Bitburg to village $a$.

outputFormat: Your programme should write out exactly $m$ integers to the standard output, one a line, denoting the numberof country roads Byteasar has travelled during his successive trips.


title: [POI2007] TET-Tetris Attack

description:
一种名为 *Tetris Attack* 的猜谜游戏风靡 Byteotia。游戏本身非常复杂，因此我们只介绍它的简化规则：

玩家拥有一个有 $2n$ 个元素的栈，一个元素放置在另一个元素上，这样一个组合有 $n$ 个不同的符号标记。对于每个符号，栈中恰好有两个元素用一个符号标记。

玩家可以交换两个相邻元素，即互换他们的位置。交换后，如果有两个相邻的元素标有相同的符号，则将他们都从栈中删除。然后，位于其上方的所有元素都会掉落下来，并且可以造成再次删除。

玩家的目标是以最少的移动次数清空堆栈。请你编写一个程序，找出最少的移动次数及方案。

inputFormat:
第一行一个整数 $n$。

接下来的 $2n$ 行里给出了栈的初始内容，第 $i+1$ 行包含一个整数 $a_i$（$1 \leq a_i \leq n $），表示从底部数起第 $i$ 个元素所标记的符号（每个符号都在栈中出现正好两次）。

最初不存在相邻的两个元素符号相同的情况，保证有不超过 $10^6$ 次操作的方案。

outputFormat:
第一行一个整数 $m$ ，表示最小的移动次数。

接下来 $m$ 行，每行输出一个数。

第 $i + 1$ 行输出 $p_i$，即表示玩家在第 $i$ 步时选择交换 $p_i$ 与 $p_{i+1}$。

如果存在多个方案，则输出其中任何一个。


title: [POI2007] KOL-Railway

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

description:
Byteland Railways encountered a necessity of restructuring and    reduction of the rail network.

After a deep analysis of of the rail network it has been decided    which railway stations will be removed and which ones will stay.

It has been also decided that the rail network should be reduced as far    as possible.

It remains to choose which railway lines should be removed and which    ones should stay.

The rail network is composed of rail segments connecting railway    stations.

It is known that from each station one can travel to every other    station (potentially visiting some intermediate stations).

Rail segments are bidirectional.

There can be at most one rail segment connecting each pair of stations.

Each segment can be assigned a cost of maintenance, which is    a positive integer.

The rail segments that will remain should be chosen in such    way that:

it is possible to travel between every pair of stations        that are not going to be removed,                  their total cost of maintenance is low (it can be at most two times        greater than the lowest cost that can be achieved, assuming that the        previous condition is satisfied).

All remaining rail segments will be removed.

Railway lines that will remain can run through stations that will be    removed.

TaskWrite a programme which:

reads a description of the rail network and the stations          that will not be removed from the standard input,                      determines which rail segments should remain and which should          be removed,                      writes out the rail segments that should remain together with the          total cost of their maintenance to the standard output.

inputFormat:
The first line of input contains two positive integers $n$ and $m$, $2\le n\le 5\ 000$, $1\le m\le 500\ 000$($m\le \frac{n(n-1)}{2}$),      separated by a single space.

$n$ denotes the number of railway stations and $m$ is the number of rail segments.

Railway stations are numbered from $1$ to $n$.

The following $m$ lines contain descriptions of the rail      segments, one per line.

Each of these lines contains three positive integers $a$,$b$ and $u$,$1\le a,b\le n$,$a\ne b$,$1\le u\le 100\ 000$.

$a$ and $b$ are the numbers of stations that are connected      by the segment and $u$ is its cost of maintenance.

The $(m+2)$'th line contains a sequence of integers separated by      single spaces.

The first one of them is $p$ - the number of stations that should remain      ($1\le p\le n$, $p\cdot m\le 15\ 000\ 000$).

It is followed by the numbers of these stations in increasing order.

outputFormat:
The first line of output should contain two integers $c$ and $k$ separated by a single space, where $c$ is the total cost of maintenance of the segments that      should remain and $k$ is the number of these segments.

Each of the following $k$ lines should contain two integers $a_i$ and $b_i$, separated by a single space -      the numbers of stations that are connected by the segment.

The total cost of maintenance of the segments can be at most      two times greater than the lowest achievable total cost.

translation:
## 题目描述

出言不逊铁路系统需要重新布置。通过对铁路网络深入的分析，有一些站点需要被移除，有一些道路也需要被移除。 整个铁路网络可以看做一张由 $n$ 个点，$m$ 条道路组成的无向图。从每一个点出发都可以通过直接或间接的道路到达其它所有点。两个站点之间最多只有一条道路。每一条道路都有一个正整数费用。你的任务是决定哪些点和道路需要被保留。 要求：

1.从每一个没被移除的点出发都能通过直接或间接的没被移除的道路到达其他所有没被移除的点。

2.剩下的道路的费用总和要比较小，即不能超过最优解的两倍。

## 输入格式

第一行包含两个正整数 $n$、$m$（$2\leq n\leq 5\times 10^3$，$1\leq m\leq 5\times 10^5$），表示点数和边数。 接下来 $m$ 行，每行包含三个正整数 $a$、$b$、$u$（$1\leq a$、$b\leq n$，$a\neq b$，$1\leq u\leq 1 \times 10^5$），表示 $a$ 和 $b$ 之间有一条费用为 $u$ 的道路。 最后一行的开头为一个正整数 $p$（$2\leq p\leq n$，$p\times m\leq 1.5\times 10^7$），表示必须要保留的点数。 接下来包含 $p$ 个正整数，按递增顺序依次给出必须保留的点的编号。

## 输出格式

第一行包含两个正整数 $c$、$k$，其中 $c$ 表示剩余道路的费用总和，$k$ 表示剩余道路的条数。 接下来 $k$ 行，每行包含两个正整数 $a$、$b$，表示一条道路的两个端点。 如有多组解，输出任意一组。


title: [POI2007] ODW-Weights

description:
While moving to a new compound the Byteotian Institute of Experimental Physics has encountered a logisticalproblem - the transfer of its vast collection of precision weights turned out to be non-trivial.

The Institute has a certain number of containers of limited strength at its disposal. As many weightsas possible are to be put into the containers, the remaining ones will be discarded. There is no limit onthe number of weights to be put in a container apart from the requirement of not exceeding its strength. Acontainer may also be empty.

Any two weights in the Institute have a peculiar property: the mass of one of them is an integer multipleof the mass of the other. Particularly, they may have the same mass.

TaskWrite a programme which:

reads the durabilities of the containers and masses of the weights from the standard input,        determines the maximal number of weights that can be put in the containers,        writes the outcome to the standard output.

inputFormat: The first line of the standard input contains two integers $n$ and $m$($1\le n,m\le 100\ 000$), separated by a singlespace, denoting respectively: the number of containers and the number of weights. The second line of thestandard input consists of $n$ integers $w_i$ ($1\le w_i\le 1\ 000\ 000\ 000$ for $1\le i\le n$), separated by single spaces,denoting the strengths of containers in milligrammes. In the third line there are $m$ integers $m_j$($1\le m_j\le 1\ 000\ 000\ 000$) for $1\le j\le m$), separated by single spaces, denoting masses of the weights in milligrammes.

outputFormat: The first and only line of the standard output should contain a single integer -the maximal number ofweights that can be placed in the containers without exceeding their durability.

translation:
在 byteotian 公司搬家的时候，他们发现他们的 $m$ 个大量的精密砝码的搬运是一件恼人的工作。公司有 $n$ 个固定容量的容器可以装这些砝码。他们想装尽量多的砝码以便搬运，并且丢弃剩下的砝码。

每个容器可以装的砝码数量没有限制，但是他们能够装的总重量不能超过每个容器的限制。第 $i$ 个容器允许装下的砝码总重为 $w_i$。一个容器也可以不装任何东西。

此外，这些砝码有一个特征。对于任意两个砝码 $i,j$，它们的重量成倍数关系，即 $m_i\mid m_j$ 或者 $m_j\mid m_i$ 或者两者都成立（即重量相等）。


title: [POI2007] EGZ-Driving Exam

description:
The Byteotian driving licence exam takes place in an area in which there are $n$ straight, parallel, unidirectional, north-oriented streets (that is the allowed driving direction is south to north). Each of the streets is exactly $m$ meters long, all of them begin and end on the same level. These streets are numbered from $1$ to $n$ starting the westernmost. There are also $p$ unidirectional, east or west-oriented streets perpendicular to the abovementioned, each one of them connecting a pair of adjacent north-oriented streets. It is also possible that an east-oriented and a west-oriented street overlap, thus forming a bidirectional one.

 ![](https://cdn.luogu.com.cn/upload/pic/6981.png)

An exemplary testing area ($n=4, m=3, p=5$).

The examiner chooses a north-oriented street, at the beginnig of which the examination starts and anothernorth-oriented street, where it is to come to an end. The task of the applicant is to drive from the starting tothe final point, observing the allowed directions.The examiner always chooses as starting point a street, from which it is possible to drive to the endpointof any other north-oriented street.The work of the examiners is a very tedious one, because they always have to start at the beginning ofone of the few suitable streets. The board of directors have decided to build a new testing area on the basis ofpre-existent plans. It has been calculated, that available funds allow for no more than $k$ east or west-orientedstreets to be built. Those new streets are to be constructed in such a way, so as to add the largest possiblenumber of potential starting points (there may or may not exist starting points on the pre-existent plan). Newstreets have to connect pairs of adjacent north-oriented streets.

## Task

Write a programme which:

- reads a description of the testing area and the number $k$ from the standard input,

- calculates the greatest number of potential new starting points for the examination, generated by adding no more than $k$ east or west-oriented streets,

- writes the outcome to the standard output.

成都的驾驶考试在一个有n条平行的自南向北的单向的道路的场地中进行。每条道路长度为m米，并且都在同一条水平线上开始和结束。街道从西向东分别编号为1到n。同样有p条单向的自西向东或自东向西的街道垂直于上面描述的街道，每一条这样的街道链接了两个相邻的自南向北的道路。当然自西向东和自东向西的道路可以重叠，那就是一个双向的街道了。

考生选择一个自南向北的道路作为他考试的起始点和另外一个自南向北的道路作为他考试的终止点。他们的考试项目是将车从开始的道路驾驶到作为终止点的道路。考生们总是选择一个可以到达所有其他街道的起始道路作为开始点。现在，考生们总是感到十分无趣因为他们只有很少的起始道路可以选择，所以教练们决定改造先有的考试场所，由于经费的限制，他们决定添加至多K条东西向的道路，使得能够选择的起始道路尽量地多。

inputFormat:
In the first line of the standard input there are four integers $n$, $m$, $p$ and $k$ ($2 \le n \le 100\ 000$, $1 \le m, k, \le 100\ 000$, $0 \le p \le 100\ 000$), separated by single spaces, denoting respectively: the number of north-oriented streets, the length of each one of them, the number of pre-existent east or west-oriented streets, the maximal number of new streets to be built. The north-oriented streets are numbered from $1$ to $n$, starting with the westernmost.

The following $p$ lines contain three integers each: $n_i$, $m_i$ and $d_i$ ($1 \le n_i \le n$, $0 \le m_i \le m$, $d_i \in \{0, 1\}$), separated by single spaces, denoting the 'th east-oriented (for $d_i=0$) or west-oriented (for $d_i=1$) street. This street connects north-oriented streets $n$ and $n+1$, intersecting them in points $m_i$ meters distant from their beginning.

outputFormat: The first and only line of the standard output should contain a single integer, denoting the maximal numberof new examination starting points generated by building no more than $k$ east or west-oriented streets. Thenewly built streets **do not have to** intersect the north-oriented streets in points, whose distance from thebeginning of the street is an integer. The newly built east or west-oriented streets may overlap, thus formingbidirectional streets.


title: [POI2007] WAG-Quaternary Balance

description:
Byteasar the dragon intends to throw a party, to which he would like to invite many guests. Byteasar wouldalso like to present each guest with an amount of gold to honour the party. Each should receive the sameamount, so that no one's pride is hurt. The dragon is going to weigh out gold for subsequent guests with abeam balance. He has different types of standard masses at his disposal, each type weighing a certain powerof four. Conveniently, Byteasar has lots of the standard masses, hence he may use any number of masses ofany type (power of four) he finds appropriate. Byteasar will always lay the gold on the left weighing basinand the masses on the right or both weighing basins. The dragon wishes to use the least number of massespossible for each weighing. Furthermore, to entertain his guests, Byteasar would like to measure out the goldin unique manner for each person (ie. using different masses or distributing them among the weighing basinsin a different way).

Since dragons' lack of arithmetic skills is legendary, Byteasar has aksed you to write a programme thatwill determine how many guests he may invite, that is, finds the maximum number of ways in which $n$ grammes of gold can be weighed out using the minimum number of masses possible. Should you fare well,you will also get your share!

TaskWrite a programme that:

reads from the standard input the amount of gold (in grammes) which Byteasar intends to present each    guest with,        calculates the number of ways in which this amount of gold can be weighed out using the minimum    number of masses possible,        writes out the remainder of dividing the result by $10^9$ to the standard output.

给定一个数 $n$，要求将 $n$ 表示成一些 $4^k$ 的数之和/差的形式，要求用的数最少，求方案数模 $10^9$ 的结果。

inputFormat:
In the first and only line of the standard input there is one positive integer $n$($1\le n<10^{1000}$).

It is the amountof gold (in grammes) which Byteasar intends to present each guest with.

outputFormat: One integer should be written out to the standard output -the remainder of dividing by $10^9$ the maximumnumber of guests Byteasar can invite (that is, the maximum number of ways in which $n$ grammes of gold canbe weighed out using the minimum number of masses possible).


title: [POI2008] CLO-Toll

description:
King Byteasar has yielded under pressure of Byteotian merchants and  hence decided to settle the issue of toll paid by them.

Byteotia consists of $n$ towns connected with $m$ bidirectional roads.

Each road connects directly two different towns and no two towns are  connected by more than one direct road.

Note that the roads may lead through tunnels or flyovers.

Until now each town in Byteotia imposed duty on everyone who  either entered or left the town.

The merchants, discontented with such situation, lodged a protest  against multiple taxation.

King Byteasar ruled that the town privileges are now restricted.

According to the new royal edict, each town can only charge toll on  merchants travelling by exact one road leading into the town,  regardless of the direction they are travelling in.

Furthermore, for each road, those who travel it cannot be made to pay  the duty to both towns the road connects.

It remains to determine which town should collect toll from which road.

Solving this problem His Highness has commissioned to you.

## Task

Write a programme that:

- reads the Byteotian road system's description from the standard input,

- for each town determines on which road it should impose toll, or claims it is impossible,

- writes out the result to the standard output.

inputFormat: There are two integers in the first line of the standard input: $n$ and $m$ ($1 \le n \le 100\ 000$, $1 \le n \le 200\ 000$), denoting the number of towns and roads in Byteotia, respectively. The towns are numbered from $1$ to $n$. In next $m$ lines descriptions of the roads follow. In line No. $i$ there are two integers $a_i$ and $b_i$ () meaning that towns $a_i$ and $b_i$ are directly connected by a road.

outputFormat: If collecting the toll in accordance with the royal edict is impossible, your programme should write the word NIE ('no' in Polish) in the first and only line of the standard output. Otherwise, it should write the word TAK ('yes' in Polish) in the first line, while in the following $n$ lines should tell which city collects toll from which road. Line no. $(i+1)$ should tell on which road the town no. $i$ imposes toll. Since town no. $i$ is obviously one endpoint of this road, it is enough to tell what is the other endpoint. Thus if the town no. $i$ imposes toll on the road connecting it with the town no.$j$ , the line no. $(i+1)$ should contain the number $j$. If more than one solution exists, write out one chosen arbitrarily.

translation:
### 题目描述

给你 $n$ 个点和 $m$ 条双向边，问能否将其中的一些边改成有向边，使得只考虑有向边的情况下每个点的入度都为 $1$ 。

### 输入格式

第一行输入 $n,m(1≤n≤100000,1≤m≤200000)$ ，接下来 $m$ 行每行两个数 $a,b$ 表示点 $a$ 和点 $b$ 之间有一条双向边。输入保证没有重边与自环。

### 输出格式

若没有合法方案，输出 $\verb!NIE!$，否则先在第一行输出 $\verb!TAK!$，然后在第 $i+1$ 行输出点 $i$ 的入度是由哪个点出发的边所得到的。

感谢@hdxrie 提供的翻译。

hint:
样例1：

 ![](https://cdn.luogu.com.cn/upload/pic/6984.png)

样例2：

![](https://cdn.luogu.com.cn/upload/pic/6985.png)


title: [POI2008] KLO-Building blocks

description:
Byteasar loved to play with building blocks as a child.

He used to arrange the blocks into $n$ columns of random height  and then organize them in the following manner:

Byteasar would choose a number $k$ and try to arrange the blocks in such a way that  some $k$ consecutive columns would be of equal height. Furthermore he always tried to  achieve this goal in a minimum number of moves possible, where a single move consists in:

laying one block on top of any column      (Byteasar had a huge box with spare blocks, ensuring this move could always be performed),      or              removing the uppermost block from the top of any column.

However, Byteasar was never quite sure if his sequence of moves was indeed optimal,  therefore he has asked you to write a programme that will help him solve the problem.

Task    Write a programme that:

reads the number $k$ along with the initial setup of the blocks from the standard input,determines the optimal solution (shortest possible sequence of moves),writes out the solution to the standard output.

有 $n$ 柱砖，每柱砖有一个高度，我们现在希望有连续 $k$ 柱的高度是一样的。

你可以选择以下两个动作：

1. 从某柱砖的顶端拿一块砖出来,丢掉不要了。
2. 从仓库中拿出一块砖，放到某一柱，仓库是无限大的。

现在希望用最小次数的动作完成任务，除此之外你还要求输出结束状态时，每柱砖的高度。

inputFormat:
In the first line of the standard input there are two integers, $n$ and $k$ ($1\le k\le n\le 100\ 000$), separated by a single space.

Each of the following $n$ lines contains the height of some column;    the line no. $i+1$ contains the integer    $0\le h_i\le 1\ 000\ 000$ - the height of the $i^{th}$ column,    ie. the number of blocks it consists of.

第一行两个用空格隔开的数表示 $n,k$。

之后 $n$ 行，第 $i+1$ 行一个数表示第 $i$ 柱砖的高度 $h_i$。

outputFormat:
The optimal solution should be written out to the standard output, ie. such arrangement    of blocks that:

contains $k$ consecutive columns of equal height,                  can be obtained from the initial setup in a minimum possible number of moves.

The output should consist of $n+1$ lines, each one containing a single integer.

The number in the first line should be the minimum number of moves needed to get    the desired arrangement.

The line no. $i+1$ (for $1\le i\le n$) should contain the number $h'_i$ -    the final height of the $i^{th}$ column.

If more than one optimal solution exists, write out one chosen arbitrarily.

输出 $n+1$ 行。

第一行一个数表示最小化的答案。

之后 $n$ 行，每行一个数表示结束后每柱砖的高度。

hint:
$1\le k\le n\le 100\ 000$，$0\le h_i\le 1\ 000\ 000$。

本题SPJ的提示说明（按照SPJ判断顺序给出）：

`Out of Range`：输出的数字不在答案可能的范围内。

`Wrong Solution`：输出方案中不包含连续k个相同高度的柱。

`Wrong Result`：提交的程序的步数和输出方案的步数不相等。

`Expected cost = a,found cost = b`：期望步数为 $a$，程序的步数为 $b$。

`OK!Correct Answer!`：答案正确。


title: [POI2008] PLA-Postering

description:
All the buildings in the east district of Byteburg were built    in accordance with the old arbitecture:

they stand next to each other with no spacing inbetween.

Together they form a very long chain of buildings of diverse    height, extending from east to west.

The mayor of Byteburg, Byteasar, has decided to have the north face    of the chain covered with posters.

Byteasar ponders over the minimum number of posters sufficient to    cover the whole north face.

The posters have rectangular shape with vertical and horizontal sides.

They cannot overlap, but may touch each other, i.e. have common points    on the sides.

Every poster has to entirely adjoin the walls of certain buildings    and the whole surface of the north face has to be covered.

Task      Write a programme that:

reads the description of buildings from the standard input,                      determines the minimum number of posters needed to entirely cover their north faces,                      writes out the outcome to the standard output.

Byteburg市东边的建筑都是以旧结构形式建造的:建筑互相紧挨着,之间没有空间.它们共同形成了一条长长的,从东向西延伸的建筑物链(建筑物的高度不一).Byteburg市的市长Byteasar,决定将这个建筑物链的一侧用海报覆盖住.并且想用最少的海报数量,海报是矩形的.海报与海报之间不能重叠,但是可以相互挨着(即它们具有公共边),每一个海报都必须贴近墙并且建筑物链的整个一侧必须被覆盖(意思是:海报需要将一侧全部覆盖,并且不能超出建筑物链)

inputFormat:
The first line of the standard input contains one integer $n$ ($1\le n\le 250\ 000$), denoting the number of buildings the chain      comprises of.

Each of the following $n$ lines contains two integers $d_i$ and $w_i$ ($1\le d_i,w_i\le 1\ 000\ 000\ 000$),      separated by a single space, denoting respectively the length and height      of the $i^{th}$ building in the row.

第一行为一个整数n(1≤n≤250000),表示有n个建筑,接下来n行中,第i行表示第i个建筑物的宽di与高wi(1≤di,wi≤1 000 000 000),中间由一个空格隔开

outputFormat:
The first and only line of the standard output should contain one integer,      the minimum number of rectangular posters that suffice to cover the north faces      of the buildings.

第一个为一个整数,表示最少需要几张海报.

hint:
题目简述：N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.

感谢@\_\_乱世魇华 提供翻译


title: [POI2008] ROB-Robinson

description:
Tossed by the storm on a deserted island, Robinson built himself a boat    so that he could go out to the sea and seek out human domicile.

He is an experienced sailor, therefore he built the boat with accordance to the rules    of craftsmanship: it has a longitudinal axis of symmetry and an appropriate    shape. The boat's prow is thin, and it widens gradually towards the boat's centre,    only to gradually narrow once again towards the stern.

In particular, at some point in the middle the boat is wider than both at the    prow and stern.

Unfortunately, Robinson has launched his boat in a most improper space: there    is extremely thick reed all around. It is, moreover, so stiff that the boat    cannot break through. Perhaps Robinson can get to the high seas by carefully    manoeuvring between the reed.

Due to lack of manoeuvrability, the boat can move forward and backward and    even sidewards (leftward or rightward), but it cannot turn.

It is thus allowed, and may be in fact necessary, that the boat moves with    its stern or broadside to the front.

You are to judge if Robinson can get to the high seas.

To make your task easier the island and its surroundings will be    represented by a square map divided into square unit fields, each    occupied by either water, part of Robinson's boat or an obstacle, eg.

land or reed. Initially the boat is set parallel to one of the cardinal    directions, ie. its longitudinal axis of symmetry is parallel to this    direction and the axis bisects the unit fields it is covered with.

We assume that the high seas starts where the map ends.

Hence Robinson may get to the high seas if his boat can leave    the area depicted in the map.

A single move consists in moving the boat to a side-adjacent    field in a chosen direction (north, south, east or west).

The move is permissible if both before and after it the boat    remains entirely in water (it does not occupy a field with an    obstacle).

Task      You are to write a programme that                        reads the map's description from the standard input,                      calculates the minimum possible number of boat's moves that          suffice to completely leave the area depicted in the map,                      writes out this number to the standard output.

被风暴抛弃在荒岛上的鲁滨逊（又译鲁滨孙）自己造了一条船，这样他就可以出海去寻找有人类居住的地方。

他是一位经验丰富的水手，因此他根据技术规程建造了它。它有一条纵向的对称轴，以及适于航行的外形：船头较尖，向船中逐渐扩宽，到船尾又逐渐收窄。

特别的是，船中的一些点比船头和船尾都宽。

可是很不幸，鲁滨逊在最不合适的位置让他的船下了水：周围有极其厚的芦苇。此外，这条船太僵硬以至于它无法突破芦苇。不过或许鲁滨逊可以通过在芦苇中小心翼翼地操纵船去往公海。

由于船太不灵活，船可以前进、后退甚至横着（向左或向右）移动，但它不能掉头。

允许船的船尾或者船舷在前进行移动，事实上这可能是必要的。

你需要判断鲁滨逊是否可以到达公海。

为了简化你的工作，岛屿和周围的环境将由一张划分成方格的正方形地图表示，每格只可能是水、鲁滨逊船的一部分或障碍物（比如说岛屿和芦苇）。最初船平行于一个主要方向（换句话说，即其纵向对称轴平行于此方向且其平分其覆盖的方格）

我们假定地图之外就是公海。

因此，如果他的船可以离开地图描绘的区域，鲁滨逊也许就能到达公海了。

一步表现为船往选定的方向（北，南，东或西）移动一格。

如果移动前后的船保持整个在水中（不占据任何有障碍物的格子），那么这个移动是合法的。

你的任务是编写一个程序，从标准输入中读取地图的描述，计算船离开地图描述的区域的最少步数，并输出至标准输出。

inputFormat:
The first line contains one integer $3\le n\le 2000$, denoting the length of the map's side.

In each of the following $n$ lines there are $n$ characters      describing successive fields of the map:

$i^{th}$ character in the $(j+1)^{th}$ line tells the contents      of the field $(i,j)$.

The following characters may appear there:

"." - (dot) denotes a field filled with water,             "X" - denotes an obstacle (land or reed),             "r" - denotes a part of Robinson's boat.
第一行一个正整数 $$3\le_n\le_2000$,$ 表示地图的边长。

接下来 $n$ 行每行 $n$ 个字符表示地图：（此处省略两张图片）第 $(j+1)$ 行的的第 $i$ 个字符表示方格 $(i,j)$。以下的字符可能会在输入中出现：`.`表示一格水，`X` 表示一格障碍物（岛屿或芦苇），`R` 表示鲁滨孙的船的一部分。

outputFormat:
Your programme should write out (in the first and only line of      the standard output) a single positive integer, equal to      the minimum number of boat's moves that suffice to completely      leave the area depicted in the map.

Should getting to the high seas be impossible, write out the word      'NIE' ('no' in Polish).

你的程序应当输出（在标准输出的第一行且仅有一行）一格正整数表示鲁滨逊的船完全离开地图标示的区域需要的最小步数。

如果鲁宾逊无法到达公海，输出一行 `NIE`（波兰语中否定的意思）


title: [POI2008] BLO-Blockade

description:
There are exactly $n$ towns in Byteotia.

Some towns are connected by bidirectional roads.

There are no crossroads outside towns, though there may be bridges,    tunnels and flyovers. Each pair of towns may be connected by at most    one direct road. One can get from any town to any other-directly    or indirectly.

Each town has exactly one citizen.

For that reason the citizens suffer from loneliness.

It turns out that each citizen would like to pay a visit to    every other citizen (in his host's hometown), and do it    exactly once. So exactly $n\cdot (n-1)$ visits should take place.

That's right, should.

Unfortunately, a general strike of programmers, who    demand an emergency purchase of software, is under way.

As an act of protest, the programmers plan to block one town of    Byteotia, preventing entering it, leaving it, and even passing through.

As we speak, they are debating which town to choose so that    the consequences are most severe.

Task    Write a programme that:

reads the Byteotian road system's description from the            standard input,           for each town determines, how many visits could take place            if this town were not blocked by programmers,           writes out the outcome to the standard output.

inputFormat:
In the first line of the standard input there are two positive    integers: $n$ and $m$ ($1\le n\le 100\ 000$, $1\le m\le 500\ 000$) denoting the number of towns and roads, respectively.

The towns are numbered from 1 to $n$.

The following $m$ lines contain descriptions of the roads.

Each line contains two integers $a$ and $b$ ($1\le a<b\le n$) and    denotes a direct road between towns numbered $a$ and $b$.

outputFormat: Your programme should write out exactly $n$ integers to the standard    output, one number per line. The $i^{th}$ line should contain the number    of visits that could not take place if the programmers blocked the town    no. $i$.

translation:
B 城有 $n$ 个城镇（从 $1$ 到 $n$ 标号）和 $m$ 条双向道路。

每条道路连结两个不同的城镇，没有重复的道路，所有城镇连通。

把城镇看作节点，把道路看作边，容易发现，整个城市构成了一个无向图。

请你对于每个节点 $i$ 求出，把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。

**【输入格式】**

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示城镇 $a$ 和 $b$ 之间存在一条道路。

**【输出格式】**

输出共 $n$ 行，每行输出一个整数。

第 $i$ 行输出的整数表示把与节点 $i$ 关联的所有边去掉以后（不去掉节点 $i$ 本身），无向图有多少个有序点 $(x,y)$，满足 $x$ 和 $y$ 不连通。

**【数据范围】**

$n\le 100000$，$m\le500000$。


title: [POI2008] BBB-BBB

description:
Byteasar has an account at The Byteotian Bit Bank (BBB in short).

At the beginning there were $p$ and at the end $q$ bythalers in the account.

Each transaction was either a deposit or a withdrawal of one bythaler.

The account's balance was never negative.

A bank teller has prepared a bank statement: a strip of paper with a sequence of pluses and minuses in it   (a plus denotes a deposit while minus a withdrawal of one bythaler).

Soon it turned out, that some transactions were not entered correctly.

The bank teller cannot print another statement, but has to correct the   one already printed instead.

The statement needs not be consistent with the truth, it will suffice if the sequence of transactions satisfies the following two conditions:

the final balance is consistent with the initial balance and the sequence of transactions in the statement, according to the sequence of transactions in the statement, the account's balance was never negative.

You are to calculate the minimum amount of time the bank teller needs to   correct the bank statement.

The bank teller can:

- in $x$ seconds turn an arbitrarily chosen transaction to its opposite, or
- in $y$ seconds remove the last transaction and put it at the beginning of the statement.

If, for example, $p=2,q=3$, then `--++-+-++-+-+` is a correct   statement.

On the other hand the statement `---++++++` is incorrect, because the account's balance would become negative after the third transaction, and furthermore the final balance should be 3, not 5.

It can be, however, corrected by turning the second to last symbol to its opposite and placing the last transaction at the beginning of the statement.

### Task

Write a programme that:

- reads the current bank statement for Byteasar's account (a sequence of pluses and minuses) as well as the numbers $p,q,x$ and $y$ from the standard input.
- writes out to the standard output the minimum number of seconds needed to correct the statement in a way such that the initial and final balance are consistent and that the balance is never negative.

inputFormat:
The first line contains 5 integers $n,p,q,x$ and $y\ (1\le n\le 1\ 000\ 000$, $0\le p,q\le 1\ 000\ 000$, $1\le x,y\le 1000$), separated by single spaces and denoting respectively:

the number of transactions done by Byteasar, initial and final account     balance and the number of seconds needed to perform a single turn     (change of sign) and move of transaction to the beginning.

The second line contains a sequence of ![](http://main.edu.pl/images/OI15/bbb-en-tex.18.png) signs (each a plus     or a minus), with no spaces in-between.

outputFormat:
The first and last output line should contain one integer,     the minimum number of seconds needed to correct the statement. If no     corrections are necessary, the number is zero.

You may assume that a proper sequence of modifications exists for each     test data.

translation:
给定一个由 $+1$ 和 $-1$ 构成的长度为 $n$ 的序列，提供两种操作：

1. 将某一位取反，花销为 $x$；
2. 将最后一位移动到第一位，花销为 $y$。

要求最终 $p+S_n=q$，且 $p+S_i≥0\ (1≤i≤n)$，求最小花销。其中 $S_i=a_1+a_2+\cdots+a_i$。


title: [POI2008] POC-Trains

description:
The Trains of Colour Parade begins tomorrow in Byteotia.

Intense preparations are already in progress at the station's auxiliary tracks. There are $n$ parallel tracks at the station, numbered from $1$ to $n$. The train no. $i$ occupies the $i^{th}$ track.

Every train consists of $l$ cars and each car is painted with one of 26 colours (denoted by non-capital letters of the English alphabet).

We say that two trains look the same, if their corresponding cars are painted the same colour.

Throughout the parade a crane will switch places of certain pairs of cars. The real parade, however, will take place tomorrow.

Today the train dispatcher, Byteasar, watched the general rehearsal    closely. He even wrote down the sequence of car swaps.

Byteasar particularly dislikes many trains looking the same.

For each train $p$ he would like to calculate the maximum number    of trains that at some moment look the same as the train $p$ at the very same moment.

## Task

Write a programme that:

- reads descriptions of the trains occupying tracks and the sequence of car swaps,

- for each train determines the maximum number of trains that look the same as it at certain moment,

- writes out the result.

给出n个字符串，长度均为len；

有m次操作，每次将两个字符交换；

求每个字符串在任何时点上，与相同的它最多的字符串个数；

inputFormat:
The first line of the input contains three integers $n$, $l$ and $m$ ($2 \le n \le 1000$, $1 \le l \le 100$, $0 \le m \le 100\ 000$), denoting respectively the number of trains, their common length and the number of car swaps. The following $n$ lines contain descriptions of the trains on successive tracks. The

$k^{th}$ line consists of $l$ small letters of the English alphabet denoting the colours of successive cars of the $k^{th}$ train. Then $m$ lines describing the car swaps follow, in the order of the swaps. The $r^{th}$ line contains four integers $p_1$, $w_1$, $p_2$, $w_2$ ($1 \le p_1, p_2, \le n$, $1 \le w_1, w_2 \le l$, $p_1 \ne p_2$ or $w_1 \ne w_2$) denoting the $r^{th}$ car swap-the car no. $w_1$ of the train no. $p_1$ is swapped with the car no. $w_2$ of the train no. $p_2$.

outputFormat: Your programme should write out exactly $n$ lines. The $k^[th}$ line should contain one integer-the number of trains looking the same as the train no. $k$ at certain moment.

hint:
The figure presents the successive car swaps:

```cpp
track 1:  ababbd    ababbd    ababbd    ababbd    aaabbd    aaabbd    aaabbd    aaabbd
track 2:  abbbbd    ababbd    ababbd    aaabbd    aaabbd    acabbd    acabbd    acabbd
track 3:  aaabad -> aaabad -> aaabad -> aaabbd -> aaabbd -> aaabbd -> aaabbd -> aaabbd
track 4:  caabbd    caabbd    caabbd    caabbd    cabbbd    cabbbd    cabbbd    dabbbd
track 5:  cabaad    cabbad    caabbd    caabbd    caabbd    aaabbd    aaabbd    aaabbc
           (0)       (1)       (2)       (3)       (4)       (5)       (6)       (7)
```

The number of trains looking the same as either of the trains no. 1, 2 or 3 was maximal at time (4) (when all three looked the same). The number of trains looking the same as the train no. 5 was maximal at time (5) and (6). The number of trains looking the same as the train no. 4 was maximal at time (2).


title: [POI2008] MAF-Mafia

description:
Mob feud rages in Equatorial Byteotia. The mob bosses have come to the country's capital, Byteburg, to settle the dispute.

Negotiations were very tense, and at one point the trigger-happy participants drew their guns.

Each participant aims at another with a pistol.

Should they go on a killing spree, the shooting will go in accordance with the following code of honour:

the participants shoot in a certain order, and at any moment at most one of them is shooting, no shooter misses, his target dies instantly, hence he may not shoot afterwards, everyone shoots once, provided he had not been shot before he has a chance to shoot, no participant may change his first target of choice, even if the target is already dead (then the shot causes no further casualties).

An undertaker watches from afar, as he usually does. After all, the mobsters have never failed to stimulate his business.

He sees potential profit in the shooting, but he would like to know tight estimations. Precisely he would like to know the minimum and maximum possible death rate.

The undertaker sees who aims at whom, but does not know the order of shooting.

You are to write a programme that determines the numbers he is so keen to know.

Task Write a programme that:

reads from the standard input what target each mobster has chosen,                        determines the minimum and maximum number of casualties, writes out the result to the standard output.

inputFormat:
The first line of the standard input contains the number of participants $n$ ($1\le n\le 1{,}000{,}000$).

They are numbered from $1$ to $n$.

The second line contains $n$ integers $s_1,s_2,\cdots,s_n$, separated by single spaces, $1\le s_i\le n$.

$s_i$ denotes the number of $i^\mathrm{th}$ participant's target.

Note that it is possible that $s_i=i$ for some $i$ (the nerves, you know).

outputFormat: Your programme should write out two integers separated by a single      space in the first and only line of the standard output. These numbers      should be, respectively, the minimum and maximum number of casualties resulting from the shooting.

translation:
有 $n$ 个参赛者，对于第 $i$ 个参赛者，他在初始时刻用手枪瞄准了一个参赛者 $\mathit{aim}_i$，（$\mathit{aim}_i$ 可以是 $i$）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。所以，对于不同的开枪顺序，最后被击中的人数也不同。

你需要求出：在所有的开枪顺序中，最少和最多的被击中人数。

对于 $100\%$ 的数据，$1\leq n \leq 10^6$，$1\leq \mathit{aim}_i \leq n$。


title: [POI2008] UCI-The Great Escape

description:
Al Bytone, the infamous thief, plans a bank robbery.

He knows only too well that the moment he robs the bank a pursuit    will be commenced. Unfortunately, Al Bytone is a poor driver and turning    left causes him great trouble. This is why he tries to devise such an    escape route that at each intersection he would either ride straight    ahead or turn right. He is also aware that once he passes through any    intersection, the police will come and remain there, waiting for him.

Therefore he may pass through any intersection at most once.

Furthermore, the police are always present at certain intersections,    so Al Bytone will have to avoid these intersections as well    (there's no police at the intersections near the bank and near Al Bytone's    hideout.)    Al Bytone is planning his escape route. To your great (and rather    unpleasant) surprise, he paid you a visit and told to calculate the    number of different escape routes leading from the bank to his hideout    complying the aforementioned requirements. Needless to say, Al Bytone    does not take 'no' as an answer...

The streets of Byteburg form a rectangular grid. Every street runs either in the North-South or East-West direction,    and every two non-parallel streets intersect. The bank is situated to the south of the south-western-most intersection.

Al Bytone will start his great escape driving north.

<Task>

Write a programme that:

reads from the standard input the location of hideout,          descriptions of intersections with police and a positive          integer ![](http://main.edu.pl/images/OI15/uci-en-tex.1.png),                      calculates the number of different escape routes leading from the bank to the hideout          complying the aforementioned requirements,                      writes out to the standard output this number's residue modulo $k$.

inputFormat:
There are three integers in the first line of the standard input, $n$, $m$ and $k$ ($1\le n,m\le 100$, $1\le k\le 10^9$).

The numbers $n$ and $m$ denote the number of streets leading in      East-West and North-South direction, respectively.

The second line contains two integers $x$ and $y$ ($1\le x\le n$, $1\le y\le m$).

These represent the hideout's location - at the intersection      of $x^{\mathrm{th}}$ street leading in Nort…

outputFormat: Your programme should write out the residue of the number of escape      routes modulo $k$ in the first and only line of the standard output.

translation: 给一个 $n\times m$ 的地图，计算从 $(n,1)$ 到第 $x$ 列的第 $y$ 行的路径条数 $\bmod k$，走过的点不能再走，转弯只能向右转。


title: [POI2008] KUP-Plot purchase

description:
Byteasar is going to buy an industrial plot.

His fortune is estimated at $k$ bythalers and this is exactly the amount    Byteasar would like to spend on the parcel.

Finding a parcel worth exactly $k$ bythalers, however, is not an easy task.

For this reason Byteasar is ready to buy a more expensive plot.

He considers taking out a loan. The Byteotian Credit Bank will grant him    a loan of up to $k$ bythalers. Thus, Byteasar can spend no more than $2k$    bythalers on the parcel and he would like to spend no less than $k$ bythalers.

The area in which Byteasar wants to buy his parcel is a square with side    length of $n$ metres. The current landlords have set up various prices per square metre. Byteasar has spoken to each one of them and has then prepared a price map    of the area. The map depicts the price of every metre by metre square. Clearly, there    are $n^2$ such squares. Now is the time to find the dream parcel. It has to be rectangular and consist of whole unit squares. Byteasar has already started looking for the plot on the map,    but after many hours he was still unable to find a suitable one. Be a chap and help him!

<Task>

Write a programme that:

reads the numbers $k$ and $n$ from the standard input,  along with the price map of the area, determines a parcel with price in the interval $[k,2k]$ or states that no such parcel exists, writes out the result to the standard output.

inputFormat:
The first line of the standard input contains two integers, $k$ and $n$, separated by a single space, $1\le k\le 10^9$, $1\le n\le 2000$.

Each of the following $n$ lines contains $n$ non-negative integers, separated by single spaces.

$i^\mathrm{th}$ number in the line no. $j+1$ denotes the price of unit square with coordinates $(i,j)$.

The price of one square metre does not exceed $2{,}000{,}000{,}000$ bythalers.

outputFormat:
If no plot with price in the interval $[k,2k]$ exists, your programme should output exactly one line with word `NIE` (NO in Polish).

Otherwise it should print out one line with four positive integers $x_1,y_1,x_2,y_2$ separated by single spaces and denoting the rectangle's      coordinates.

$(x_1,y_1)$ denotes the upper left rectangle corner, while $(x_2,y_2)$ the lower right corner.

Then it consists of the squares: $\{x,y\mid x_1\le x\le x_2,y_1\le y\le y_2\}$.

The sum $c$ of prices of the squares forming up this rectangle should satisfy the inequality $k\le c\le 2k$.

If more than one rectangular parcel satisfies this condition, pick one arbitrarily.

hint:
给定 $k,n$ 和 $n\times n$ 的矩阵，求一个子矩形满足权值和在 $[k,2k]$ 之间。

$n<2000$，$1\le k\le10^9$，每个价格都是不大于$2 \times 10^9$ 的非负整数。

感谢@cn：苏卿念 提供的spj


title: [POI2008] POD-Subdivision of Kingdom

background: [English Edition](/paste/eu7u3hqg)

description: 给出一张有 $n$ 个点 $m$ 条边的无向图，你需要求出一组合法的方案，使得图被划分为点数均为 $\frac n2$ 的两个集合，且两个端点在不同集合中的边数最少。

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

之后 $m$ 行，每行两个整数 $a, b$，表示在 $a$ 与 $b$ 之间有一条边。

outputFormat: 一行 $\frac n2$ 个整数，表示在你求出的方案中的一个集合的所有点，由编号从小到大排序。

hint: 对于 $100\%$ 的数据，$1\le n\le 26$，$1\le a,b\le n$，且 $n$ 为偶数。保证没有重边。


title: [POI2008] TRO-Triangles

description:
$n$ pairwise disjoint points in the plane are given ($n\ge 3$).

There are $\dfrac{n(n-1)(n-2)}{6}$ triangles whose    vertices are some pairwise different points among them    (including degenerate triangles, i.e. ones whose vertices are collinear).

We want to calculate the sum of areas of all the triangles with vertices    in the given points.

Those parts of the plane that belong to many triangles are to be calculated    multiple times. We assume that the area of degenerate triangles (i.e. those    with collinear vertices) is zero.

<Task>

Write a programme that:

reads from the standard input the coordinates of the points in the plane,                 determines the sum of the areas of all the triangles with vertices in       the given points,                  prints out the result to the standard output.

inputFormat:
In the first line of the standard input there is one integer $n$ ($3\le n\le 3000$) denoting the number of selected points.

Each of the following $n$ lines contains two integers $x_i$ and $y_i$ ($0\le x_i,y_i\le 10^4$) separated by a single space and denoting   the coordinates of the $i^\mathrm{th}$ point (for $i=1,2,\cdots,n$).

No pair (ordered) of coordinates appears more than once.

outputFormat: In the first and only line of the standard output there should be one   real number equal to the sum of the areas of all the triangles with   vertices in the given points. The outcome should be printed out with   exactly one digit after dot and should not differ from the correct value   by more than $0.1$.

translation: 给定平面上的一些点，求这些点能组成的所有三角形的面积之和。


title: [POI2008] PER-Permutation

description:
Multiset is a mathematical object similar to a set,    but each member of a multiset may have more than one membership.

Just as with any set, the members of a multiset can be ordered    in many ways. We call each such ordering a permutation    of the multiset. For example, among the permutations of the    multiset{1,1,2,3,3,3,7,8}. there are {2,3,1,3,3,7,1,8}   and{8,7,3,3,3,2,1,1}.

We will say that one permutation of a given multiset is smaller    (in lexicographic order) than another permutation, if on the first    position that does not match the first permutation has a smaller    element than the other one. All permutations of a given multiset    can be numbered (starting from one) in an increasing order.

Task      Write a programme that   reads the description of a permutation of a multiset and a positive          integerm from the standard input,                      determines the remainder of the rank of that permutation in the          lexicographic ordering modulo m,         writes out the result to the standard output.

多重集合是数学中的一个概念，它的定义很像集合，但是在多重集之中，同一个元素可以出现多次。

和集合一样，多重集的的元素可以有很多种元素的排布顺序。我们把它叫作多重集的排列。

现在我们定义多重集的某个排列$s_i$比某个排列$s_j$

的大小比较为字典序比较。这样某个多重集的排列可以从小到大得排起来。

现在给你一个元素个数为n的多重集的一个排列和m，求这个排列的排名取模m。

inputFormat:
The first line of the standard input holds two integers n($1\le n \le 300000$) and m  ($2 \le m \le 10^9$ ) ,separated by      a single space. These denote, respectively, the cardinality of the      multiset and \dots\ the number m.

The second line of the standard input contains n positive integers      $a_i$($1\le a_i \le 300000$), separated by single spaces and denoting      successive elements of the multiset permutation.

第一行 两个整数n,m

第二行 n个数，代表多重集的排列

outputFormat:
The first and only line of the standard output is to hold one integer,      the remainder modulo m of the rank of the input permutation in the      lexicographic ordering.

一行一个整数 排名取模m

hint: 感谢@远航之曲 贡献的翻译


title: [POI2008] STA-Station

description:
给定一个 $n$ 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

一个结点的深度之定义为该节点到根的简单路径上边的数量。

inputFormat:
第一行有一个整数，表示树的结点个数 $n$。
接下来 $(n - 1)$ 行，每行两个整数 $u, v$，表示存在一条连接 $u, v$ 的边。

outputFormat:
**本题存在 Special Judge**。

输出一行一个整数表示你选择的结点编号。如果有多个结点符合要求，输出任意一个即可。

hint:
#### 样例 1 解释

输出 $7$ 和 $8$ 都是正确答案。

#### 数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 10^6$，$1 \leq u, v \leq n$，给出的是一棵树。


title: [POI2009] GAS-Fire Extinguishers

description:
Byteasar has had a new palace built. It consists of $n$ chambers and $n-1$ corridors connecting them. Each corridor connects exactly two chambers. The rooms are numbered from $1$ to $n$. There is only a single entrance to the palace, which leads to chamber no. $1$). For each chamber there is exactly one route leading to it from the entrance, without turning back on the way. In other words, the chambers and the corridors form a tree - a connected acyclic graph.

The fire marshal who is to approve the building demands placing fire extinguishers inside.

The following are his exact requirements:

- The fire extinguishers should be placed in (some) chambers, and one chamber  may store any number of extinguishers.
- Each chamber has to be assigned one fire extinguisher, though it may be stored  in another chamber.
- Each fire extinguisher can be assigned to at most $S$ different chambers.
- For each room its assigned extinguisher is within the range of $K$ corridors.

Byteasar has a week spot for lavish palaces, so it is no surprise he has very little money now, right after completion of another splendid palace.

Therefore he is interested in the minimum number of fire extinguishers sufficient  for satisfying fire marshal's demands.

inputFormat:
The first line of the standard input contains three integers $n$, $s$ and $k$ separated by single spaces, $1\le n\le 10^5$, $1\le s\le n$, $1\le k\le 20$.

Each of the following $n-1$ lines holds two integers separated by a single space.

Line no. $i+1$ contains the numbers $x_i,y_i$ denoting the corridor connecting chambers no.$x_i$ and $y_i$.

outputFormat: The first and only line of the standard output is to hold one integer - the minimum number of fire extinguishers that have to be installed in palace.

translation:
Byteasar 建好了一个宫殿。

这个宫殿有 $n$ 个房间，由 $n-1$ 条走廊连接，每一个走廊连接两个房间。

房间编号由 $1$ 到 $n$，整个宫殿只有一个入口，对于每个房间都有一条唯一的路径到达。

换句话说，这是一棵树。

接下来要在这棵树上放灭火器，并遵循以下规则：

1. 每个点至少需要被一个灭火器覆盖，但这个灭火器不一定在这个点上；
2. 每个灭火器可以最多覆盖 $s$ 个不同的点；
3. 每个灭火器最远可以覆盖距离为 $k$ 的点。

一个点可以放多个灭火器。

现在Byteasar很穷，所以让你求出最少需要放置多少灭火器。


title: [POI2009] KAM-Pebbles

description:
Johny and Margaret are playing "pebbles". Initially there is a certain number of pebbles on a table, grouped in $n$ piles. The piles are next to each other, forming a single row. The arrangement of stones satisfies an additional property that each pile consists of at least as many pebbles as the one to the left (with the obvious exception of the leftmost pile). The players alternately remove any number of pebbles from a single pile of their choice. They have to take care, though, not to make any pile smaller than the one left to it. In other words, the piles have to satisfy the initial property after the move as well. When one of the players cannot make a move (i.e. before his move there are no more pebbles on the table), he loses. Johny always starts, to compensate for Margaret's mastery in this game.

In fact Margaret is so good that she always makes the best move, and wins the game whenever she has a chance. Therefore Johny asks your help - he would like to know if he stands a chance of beating Margaret with a particular initial arrangement. Write a programme that determines answers to Johny's inquiries.

inputFormat:
In the first line of the standard input there is a single integer $u$ ($1\le u\le 10$) denoting the number of initial pebble arrangements to analyse.

The following $2u$ lines contain descriptions of these arrangements; each one takes exactly two lines.

The first line of each description contains a single integer $n$, $1\le n\le 1000$  - the number of piles.

The second line of description holds  non-negative integers  separated by single spaces and denoting the numbers of pebbles in successive piles, left to right.

These numbers satisfy the following inequality $a_1\le a_2\le \cdots \le a_n$.

The total number of pebbles in any arrangement does not exceed $1000$.

outputFormat:
Precisely $n$ lines should be printed out on the standard output.

The $i$-th of these lines (for $1\le i\le u$) should hold the word TAK (yes in Polish), if Johny can win starting with the $i$-th initial arrangement given in the input, or the word NIE (no in Polish), if Johny is bound to lose that game, assuming optimal play of Margaret.

translation:
有 $N$ 堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。

### 输入格式

多组输入，第一行一个整数 $u$ 代表数据组数（$1\le u\le 10$）

接下来共 $2u$ 行，每两行代表一组数据：

第一行只有一个整数 $n$（$1\le n\le 1000$），表示石子堆数；

第二行有 $n$ 个整数用空格隔开，第 $i$ 个整数 $a_i$ 表示第 $i$ 堆的石子个数，保证 $a_1\le a_2\le a_3\le \cdots\le a_n$。

对于每组数据，保证石子总数不超过 $10000$。

### 输出格式

输出 $u$ 行，如果第 $i$ 组数据先手必胜，输出 `TAK`，否则输出 `NIE`。


title: [POI2009] PRZ-Algorithm Speedup

description:
As a punishment for misbehaving, Byteasar is to calculate a certain mysterious and nasty Boolean-valued function $F(x,y)$, which is defined for a pair of positive integer sequences $x=(x_1,x_2,\cdots,x_n)$, $y=(y_1,y_2,\cdots,y_n)$ as follows:

- boolean $F(x, y)$
- if $W(x)\neq W(y)$ then return $0$
- else if $|W(x)|=|W(y)|=1$ then return $1$
- else return $F(p(x), p(y)) \wedge F(s(x), s(y))$.

Where:

- $W(x)$ denotes the set of members of the sequence $x$ (order and repetitions of elements are insignificant),
- $p(x)$ denotes the longest prefix (initial part of any length) of the sequence $x$, such that $W(x)\neq W(p(x))$,
- $s(x)$ denotes the longest suffix (final part of any length) of the sequence $x$, such that $W(x)\neq W(s(x))$,
- $\wedge$ denotes the logical conjunction, $1$ - true, $0$ - false,      and $|z|$ - cardinality of set $z$.

For example, for the sequence $x=(2,3,7,2,7,4,7,2,4)$ we have: $W(x)=\{2,3,4,7\}$, $p(x)=(2,3,7,2,7)$, $s(x)=(7,2,7,4,7,2,4)$. For very large data a programme calculating values of the function $F$ directly from definition is too slow by any standards. Therefore you are to make these calculations as fast as possible.

Write a programme that reads several pairs of sequences $(x,y)$ from the standard input and    prints out the values $F(x,y)$ on the standard output for every input pair.

inputFormat:
The first line of the standard input contains one integer $k$ ($1\le k\le 13$) denoting the number of sequence pairs to analyse.

Next $3k$ line hold descriptions of test cases.

The first line of each description contains two integers $n$ and $m$ ($1\le n,m\le 100{,}000$) separated by a single space and denoting the lengths of the first and second sequence, respectively.

The second line holds $n$ integers $x_i$ ($1\le x_i\le 100$) that form the sequence $x$, separated by single spaces.

The third line holds $m$ integers $y_i$ ($1\le y_i\le 100$),    that form the sequence $y$, separated by single spaces.

outputFormat: The output should consist of exactly $k$ lines; the $i$-th line (for $1\le i\le k$) should contain a single integer - 0 or 1 - the value of $F(x, y)$ for $i$-th test case.

translation:
你的任务是计算一个函数F(x, y)，其中x和y是两个正整数序列。F的定义如下：

```cpp
boolean F(x, y)
if W(x) ≠ W(y) then return 0
else if |W(x)| = |W(y)| = 1 then return 1
else return F(p(x), p(y)) AND F(s(x), s(y)).
W(x)表示序列x中元素的集合。（元素的顺序和出现次数将被无视）
p(x)表示序列x的最长前缀，满足：W(x) ≠ W(p(x))
s(x)表示序列x的最长后缀。满足：W(x) ≠ W(s(x))
|Z|表示集合Z中元素个数
```