MICHIISOFT COURSE

Cho đồ thị như hình dưới:

Tìm tổng số đường đi từ đỉnh tới đỉnh bất kỳ

Gợi ý: Với đồ thị trên xây dựng đồ thị bằng ma trận 2 chiều như này

0 1 0 1 0 0 0

1 0 1 1 0 1 1

0 1 0 1 1 1 0

1 1 1 0 1 0 0

0 0 1 1 0 0 1

0 1 1 0 0 0 0

0 1 0 0 1 0 0

Sau đó sử dụng DFS hoặc BFS để tìm tất cả đường đi có thể có trong ma trận trên

Input

Nhập vào 2 số nguyên là đỉnh bắt đầu và đỉnh kết thúc của đồ thị.

Output

Số đường đi có thể có từ đỉnh đầu đến đỉnh cuối

Example

Input:
1 4

Output:
9
giải thích:
các đường đi từ đỉnh 1 đến đỉnh 4
1 => 2 => 4
1 => 3 => 4
1 => 6 => 4
1 => 3 => 2 => 4
1 => 5 => 2 => 4
1 => 0 => 3 => 4
1 => 2 => 3 => 4
1 => 0 => 3 => 2 => 4
1 => 5 => 2 => 3 => 4