Secret Numbers

During this year's nationwide computer science conference dinner, there are ~N~ scientists in attendance. However, it seems that they are less interested in food and more interested in the intellectual nourishment opportunities provided. Thus, the problem arises that you need to solve...

Problem

Each of the N scientists attending the dinner has a positive integer in mind, different from the numbers of all their colleagues, which they keep secret. The organizer of the dinner wants to divide the scientists into groups, consisting of one or more members, so that in no group, there are two scientists whose secret number exactly divides the secret number of the other. Without knowing the scientists' secret numbers, he needs your help to calculate how many groups he will need to create.

You put your best effort into helping him. It is impossible to learn the scientists' secret numbers. With great effort, you manage to find some pairs of scientists who are friends and for whom you are certain that the secret number of the first scientist evenly divides the secret number of the second scientist.

Can you calculate the minimum number of groups the dinner organizer will need to create?

Input Files

The input files, named scidinner.in, are text files with the following structure: The first line contains two natural numbers ~N~ and ~M~ separated by a space ~(1 \le M \le N \le 1.000.000)~, where ~N~ is the number of scientists, and ~M~ is the number of pairs of friends. We assume that the scientists are numbered from ~1~ to ~N~. Each of the next ~M~ lines contains two natural numbers ~x_i~ and ~y_i~ separated by a space ~(1 \le x_i, y_i \le N)~, defining a pair of friends: we know that the secret number of scientist ~x_i~ evenly divides the secret number of scientist ~y_i~. There will be no two pairs with the same ~y_i~.

Output Files

The output files, named scidinner.out, are text files with the following structure: They have exactly one line containing an integer ~K\;(1 \le K \le N)~. This number expresses the minimum number of groups of scientists that the dinner organizer must create.

Examples of input - output files

1st:

STDIN (scidinner.in)

5 3
1 2
2 3
1 4

STDOUT (scidinner.out)

3

Explanation: At least three teams will be needed (possibly more, depending on the secret numbers of the scientists). For example, if the secret numbers are ~2~, ~4~, ~16~, ~10~, and ~3~ (in order), a possible arrangement into three teams could be: {~2~}, {~16~, ~3~}, {~4~, ~10~}.

2nd:

STDIN (scidinner.in)

12 9
1 3
1 5
1 6
5 7
11 8
8 9
6 10
6 11
4 12

STDOUT (scidinner.out)

5

Maximum Execution Time: 1 sec.