Unique Folder Structures

You are given a list of file paths. Your task is to determine the unique parent folder structures that contain these files. In other words, for each file path, you must extract the directory (i.e. the path excluding the file name) and then output the number of unique directories and the directories themselves in lexicographical order.

Note: The input will be read from standard input (stdin) and the output must be written to standard output (stdout). The folder structure should be determined by removing the last substring after the final '/' character in each path.

For example, given the paths:

/root/folderA/folderB/file1.txt
/root/folderC/folderD/file2.txt
/root/folderA/folderB/file3.txt

The unique folder structures are:

/root/folderA/folderB
/root/folderC/folderD

inputFormat

The input is provided via standard input (stdin). The first line contains an integer n representing the number of file paths. Each of the following n lines contains a file path as a string.

outputFormat

Output the number of unique folder structures on the first line. Then, output each unique folder (the parent directory) on a new line in lexicographically sorted order.## sample

7
/root/folderA/folderB/file1.txt
/root/folderC/folderD/file2.txt
/root/folderA/folderB/file3.txt
/root/folderC/folderD/file4.txt
/root/folderX/folderY/file1.txt
/root/folderX/folderY/file5.txt
/root/folderA/folderB/file6.txt

3
/root/folderA/folderB
/root/folderC/folderD
/root/folderX/folderY