﻿ Fuzhou University OnlineJudge ﻿
Problem 1799 Neighbor Friend

## Problem Description

Suppose we sort N persons in a line according to their heights,we are curious about the Neighbor Friend. A pair of Neighbor Friend is two person next to each other in the line,ignoring the order(ie (x,y) and (y,x)is the same). Now you are given M pieces of infomation,each with two integer a and b,discribing that person a is shorter than person b. Can you find how many different pairs of Neighbor Friend that could occur in some of the sorted line?

## Input

Input contains multiple cases. Each test case starts with two integer N(2<=N<=200) ,M(0<=M<1000) ,indicating that there are N persons and M pieces of information.Follow by M lines,each line contains two integers a and b,represents that person a is shorter than person b.

## Output

For each test case, output the different pairs of Neighbor Friend that could occur in some of the sorted line.

## Sample Input

3 1 1 2 3 2 1 2 2 3

3 2

## Hint

In sample 1,we know that person 1 is shorter than person 2, there may be three kind of sorted results: 3 1 2,1 3 2,1 2 3.(1,3),(1,2) and (2,3) could be found among them. In sample 2,we know that person 1 is shorter than person 2,and person 2 is shorter than person 3, so there is only one kind of sorted results:1 2 3.We can’t find (1,3),so the answer is 2.

## Source

Multi-School Training Contest - FOJ Site #7

Submit  Back  Status  Discuss
﻿